nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

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

verfasst von : Yi Fan, Chengqian Li, Zongjie Ma, Lian Wen, Abdul Sattar, Kaile Su

Erschienen in: AI 2016: Advances in Artificial Intelligence

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Improving and Extending the HV4D Algorithm for Calculating Hypervolume Exactly

Nächstes Kapitel Cascade Bayesian Optimization

https://github.com/Fan-Yi/Local-Search-for-Maximum-Vertex-Weight-Clique-on-Large-Sparse-Graphs-with-Efficient-Data-Structures.

http://www.graphrepository.com/networks.php.

In [27], both solvers are incorporated with a heuristic named BMS to solve large instances. For simplicity, we write them as MN/TS and LSCC for short.

For any vertices u and v, we use \(u = v\) to denote that u and v are the same vertex.

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

Babel, L.: A fast algorithm for the maximum weight clique problem. Computing 52(1), 31–38 (1994). http://dx.doi.org/10.1007/BF02243394MathSciNetCrossRefMATH

Balasundaram, B., Butenko, S.: Graph domination, coloring and cliques in telecommunications. In: Resende, M.G.C., Pardalos, P.M. (eds.) Handbook of Optimization in Telecommunications, pp. 865–890. Springer, Heidelberg (2006)CrossRefMATH

Ballard, D.H., Brown, C.M.: Computer Vision, 1st edn. Prentice Hall Professional Technical Reference, New York (1982)

Barabasi, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). http://www.sciencemag.org/cgi/content/abstract/286/5439/509MathSciNetCrossRefMATH

Battiti, R., Protasi, M.: Reactive local search for the maximum clique problem. Algorithmica 29(4), 610–637 (2001)MathSciNetCrossRefMATH

Bomze, I.M., Pelillo, M., Stix, V.: Approximating the maximum weight clique using replicator dynamics. IEEE Trans. Neural Netw. Learn. Syst. 11(6), 1228–1241 (2000). http://dx.doi.org/10.1109/72.883403CrossRef

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). http://dx.doi.org/10.1109/CVPR.2011.5995395

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, S.: A new trust region technique for the maximum weight clique problem. Discrete Appl. Math. 154(15), 2080–2096 (2006). http://dx.doi.org/10.1016/j.dam.2005.04.010MathSciNetCrossRefMATH

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). http://dx.doi.org/10.3233/978-1-61499-419-0-303

15.

Feige, U.: Approximating maximum clique by removing subgraphs. SIAM J. Discret. Math. 18(2), 219–225 (2005). http://dx.doi.org/10.1137/S089548010240415XMathSciNetCrossRefMATH

16.

Johnson, D.J., Trick, M.A. (eds.): Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge, Workshop, October 11–13, 1993. American Mathematical Society, Boston (1996)MATH

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). http://dx.doi.org/10.1109/CVPR.2012.6247735

20.

Miller, B.L., Goldberg, D.E.: Genetic algorithms, tournament selection, and the effects of noise. Complex Syst. 9(3), 193–212 (1995)MathSciNet

21.

Östergård, P.R.J.: A new algorithm for the maximum-weight clique problem. Nord. J. Comput. 8(4), 424–436 (2001). http://www.cs.helsinki.fi/njc/References/ostergard2001:424.htmlMathSciNetMATH

22.

Pullan, W.J.: Approximating the maximum vertex/edge weighted clique using local search. J. Heuristics 14(2), 117–134 (2008). http://dx.doi.org/10.1007/s10732-007-9026-2CrossRefMATH

23.

Ravetti, M.G., Moscato, P.: Identification of a 5-protein biomarker molecular signature for predicting alzheimer’s disease. PLoS ONE 3(9), e3111 (2008)CrossRef

24.

Rossi, R.A., Ahmed, N.K.: Coloring large complex networks. Soc. Netw. Analys. Min. 4(1), 228 (2014). http://dx.doi.org/10.1007/s13278-014-0228-yCrossRef

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., Glover, F.: Multi-neighborhood tabu search for the maximum weight clique problem. Ann. OR 196(1), 611–634 (2012). http://dx.doi.org/10.1007/s10479-012-1124-3MathSciNetCrossRefMATH

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)

Titel: Local Search for Maximum Vertex Weight Clique on Large Sparse Graphs with Efficient Data Structures
verfasst von: Yi Fan
Chengqian Li
Zongjie Ma
Lian Wen
Abdul Sattar
Kaile Su
Verlag: Springer International Publishing
Buch: AI 2016: Advances in Artificial Intelligence
Print ISBN: 978-3-319-50126-0

Electronic ISBN: 978-3-319-50127-7

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-50127-7_21

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner