Article

Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures

Authors:

Kaile SuAuthors Info & Claims

AI 2016: Advances in Artificial Intelligence: 29th Australasian Joint Conference, Hobart, TAS, Australia, December 5-8, 2016, Proceedings

Pages 255 - 267

https://doi.org/10.1007/978-3-319-50127-7_21

Published: 05 December 2016 Publication History

Abstract

The Maximum Vertex Weight Clique (MVWC) problem is a generalization of the Maximum Clique problem, which exists in many real-world applications. However, it is NP-hard and also very difficult to approximate. In this paper we developed a local search MVWC solver to deal with large sparse instances. We first introduce random walk into the multi-neighborhood greedy search, and then implement the algorithm with efficient data structures. Experimental results showed that our solver significantly outperformed state-of-the-art local search MVWC solvers. It attained all the best-known solutions, and found new best-known solutions on some instances.

References

[1]

Amgalan B and Lee H Wmaxc: a weighted maximum clique method for identifying condition-specific sub-network PLoS ONE 2014 9 8 e104993

[2]

Babel LA fast algorithm for the maximum weight clique problemComputing199452131-38http://dx.doi.org/10.1007/BF02243394

[3]

Balasundaram B and Butenko S Resende MGC and Pardalos PM Graph domination, coloring and cliques in telecommunications Handbook of Optimization in Telecommunications 2006 Heidelberg Springer 865-890

[4]

Ballard DH and Brown CM Computer Vision 1982 1 New York Prentice Hall Professional Technical Reference

[5]

Barabasi AL and Albert R Emergence of scaling in random networks Science 1999 286 5439 509-512 http://www.sciencemag.org/cgi/content/abstract/286/5439/509

[6]

Battiti R and Protasi M Reactive local search for the maximum clique problem Algorithmica 2001 29 4 610-637

[7]

Bomze IM, Pelillo M, and Stix VApproximating the maximum weight clique using replicator dynamicsIEEE Trans. Neural Netw. Learn. Syst.20001161228-1241http://dx.doi.org/10.1109/72.883403

[8]

Brendel, W., Amer, M.R., Todorovic, S.: Multiobject tracking as maximum weight independent set. In: 24th IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2011, Colorado Springs, CO, USA, 20–25 June 2011, pp. 1273–1280 (2011). https://doi.org/10.1109/CVPR.2011.5995395

[9]

Brendel, W., Todorovic, S.: Segmentation as maximum-weight independent set. In: Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6–9 December 2010, Vancouver, British Columbia, Canada, pp. 307–315 (2010). http://papers.nips.cc/paper/3909-segmentation-as-maximum-weight-independent-set

[10]

Busygin SA new trust region technique for the maximum weight clique problemDiscrete Appl. Math.2006154152080-2096http://dx.doi.org/10.1016/j.dam.2005.04.010

[11]

Cai, S.: Balance between complexity and quality: local search for minimum vertex cover in massive graphs. In: Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI 2015, Buenos Aires, Argentina, 25–31 July 2015, pp. 747–753 (2015). http://ijcai.org/papers15/Abstracts/IJCAI15-111.html

[12]

Chung, F., Lu, L.: Complex Graphs and Networks, vol. 107. American Mathematical Society (2006). https://books.google.com.au/books?id=BqqDsEKlAE4C

[13]

Eubank, S., Kumar, V.S.A., Marathe, M.V., Srinivasan, A., Wang, N.: Structural and algorithmic aspects of massive social networks. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, 11–14 January 2004, pp. 718–727 (2004). http://dl.acm.org/citation.cfm?id=982792.982902

[14]

Fang, Z., Li, C., Qiao, K., Feng, X., Xu, K.: Solving maximum weight clique using maximum satisfiability reasoning. In: 21st European Conference on Artificial Intelligence, ECAI 2014, 18–22 August 2014, Prague, Czech Republic - Including Prestigious Applications of Intelligent Systems (PAIS 2014), pp. 303–308 (2014). https://doi.org/10.3233/978-1-61499-419-0-303

[15]

Feige UApproximating maximum clique by removing subgraphsSIAM J. Discret. Math.2005182219-225http://dx.doi.org/10.1137/S089548010240415X

[16]

Johnson DJ and Trick MA Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993 1996 Boston American Mathematical Society

[17]

Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of a Symposium on the Complexity of Computer Computations, 20–22 March 1972. At the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, pp. 85–103 (1972). http://www.cs.berkeley.edu/luca/cs172/karp.pdf

[18]

Li, N., Latecki, L.J.: Clustering aggregation as maximum-weight independent set. In: Advances in Neural Information Processing Systems 25: 26th Annual Conference on Neural Information Processing Systems 2012. Proceedings of a meeting held 3–6 December 2012, Lake Tahoe, Nevada, United States, pp. 791–799 (2012). http://papers.nips.cc/paper/4731-clustering-aggregation-as-maximum-weight-independent-set

[19]

Ma, T., Latecki, L.J.: Maximum weight cliques with mutex constraints for video object segmentation. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, 16–21 June 2012, pp. 670–677 (2012). https://doi.org/10.1109/CVPR.2012.6247735

[20]

Miller BL and Goldberg DE Genetic algorithms, tournament selection, and the effects of noise Complex Syst. 1995 9 3 193-212

[21]

Östergård PRJ A new algorithm for the maximum-weight clique problem Nord. J. Comput. 2001 8 4 424-436 http://www.cs.helsinki.fi/njc/References/ostergard2001:424.html

[22]

Pullan WJApproximating the maximum vertex/edge weighted clique using local searchJ. Heuristics2008142117-134http://dx.doi.org/10.1007/s10732-007-9026-2

[23]

Ravetti MG and Moscato P Identification of a 5-protein biomarker molecular signature for predicting alzheimer’s disease PLoS ONE 2008 3 9 e3111

[24]

Rossi RA and Ahmed NKColoring large complex networksSoc. Netw. Analys. Min.201441228http://dx.doi.org/10.1007/s13278-014-0228-y

[25]

Rossi, R.A., Ahmed, N.K.: The network data repository with interactive graph analytics and visualization. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015)

[26]

Rossi, R.A., Gleich, D.F., Gebremedhin, A.H., Patwary, M.M.A.: Fast maximum clique algorithms for large graphs. In: 23rd International World Wide Web Conference, WWW 2014, Seoul, Republic of Korea, 7–11 April 2014, Companion Volume, pp. 365–366 (2014). http://doi.acm.org/10.1145/2567948.2577283

[27]

Wang, Y., Cai, S., Yin, M.: Two efficient local search algorithms for maximum weight clique problem. In: Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, 12–17 February 2016, Phoenix, Arizona, USA, pp. 805–811 (2016). http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/11915

[28]

Wu Q, Hao J, and Glover FMulti-neighborhood tabu search for the maximum weight clique problemAnn. OR20121961611-634http://dx.doi.org/10.1007/s10479-012-1124-3

[29]

Xu, K., Boussemart, F., Hemery, F., Lecoutre, C.: A simple model to generate hard satisfiable instances. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence, IJCAI 2005, pp. 337–342. Morgan Kaufmann Publishers Inc., San Francisco (2005). http://dl.acm.org/citation.cfm?id=1642293.1642347

[30]

Yamaguchi, K., Masuda, S.: A new exact algorithm for the maximum weight clique problem. In: ITC-CSCC: 2008, pp. 317–320 (2008)

Cited By

Fan YLai YLi CLi NMa ZZhou JLatecki LSu K(2019)Efficient Local Search for Minimum Dominating Sets in Large GraphsDatabase Systems for Advanced Applications10.1007/978-3-030-18579-4_13(211-228)Online publication date: 22-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-18579-4_13
Rao CFan YSu KLatecki L(2019)Common Object Discovery as Local Search for Maximum Weight Cliques in a Global Object Similarity GraphDiscrete Geometry for Computer Imagery10.1007/978-3-030-14085-4_18(219-233)Online publication date: 26-Mar-2019
https://dl.acm.org/doi/10.1007/978-3-030-14085-4_18

Index Terms

Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures

Index terms have been assigned to the content through auto-classification.

Recommendations

Solving the maximum clique problem by k-opt local search
SAC '04: Proceedings of the 2004 ACM symposium on Applied computing

This paper presents a local search algorithm based on variable depth search, called the k-opt local search, for the maximum clique problem. The k-opt local search performs add and drop moves, each of which can be interpreted as 1-opt move, to search a k-...
A CPU-GPU local search heuristic for the maximum weight clique problem on massive graphs

We propose a new neighborhood structure for the problem. The results demonstrate that our neighborhood structure is better than the current ones, and it has the additional benefit that it can be explored using a GPU-based massively parallel ...
An efficient local search for partial vertex cover problem

In this paper, an efficient local search framework, namely GRASP-PVC, is proposed to solve the minimum partial vertex cover problem. In order to speed up the convergence, a novel least-cost vertex selecting strategy is applied into GRASP-PVC. As far as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

AI 2016: Advances in Artificial Intelligence: 29th Australasian Joint Conference, Hobart, TAS, Australia, December 5-8, 2016, Proceedings

Dec 2016

727 pages

ISBN:978-3-319-50126-0

DOI:10.1007/978-3-319-50127-7

Editors:
Byeong Ho Kang
https://ror.org/01nfmeh72University of Tasmania, Hobart, Australia
,
Quan Bai
Auckland University of Technology, Auckland, New Zealand

© Springer International Publishing AG 2016.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 December 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Fan YLai YLi CLi NMa ZZhou JLatecki LSu K(2019)Efficient Local Search for Minimum Dominating Sets in Large GraphsDatabase Systems for Advanced Applications10.1007/978-3-030-18579-4_13(211-228)Online publication date: 22-Apr-2019
https://dl.acm.org/doi/10.1007/978-3-030-18579-4_13
Rao CFan YSu KLatecki L(2019)Common Object Discovery as Local Search for Maximum Weight Cliques in a Global Object Similarity GraphDiscrete Geometry for Computer Imagery10.1007/978-3-030-14085-4_18(219-233)Online publication date: 26-Mar-2019
https://dl.acm.org/doi/10.1007/978-3-030-14085-4_18

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents