Part of the book series:Lecture Notes in Computer Science ((LNISA,volume 11446))
Included in the following conference series:
3977Accesses
Abstract
Maximal Clique Enumeration (MCE) is one of the most fundamental problems in graph theory, and it has extensive applications in graph data analysis. The state-of-art approach (called as\(MCE_{degeneracy}\) in this paper) that solves MCE problem in real-world graphs first computes the degeneracy ordering of the vertices in a given graph, and then for each vertex, conducts the\(BK_{pivot}\) algorithm in its neighborhood (called asdegeneracy neighborhood in this paper). In real-world graphs, the process of degeneracy ordering produces a large number of dense degeneracy neighborhoods. But, the\(BK_{pivot}\) algorithm, with its down-to-top nature, adds just one vertex into the result set at each level of recursive calls, and cannot efficiently solve the MCE problem in these dense degeneracy neighborhoods.
In this paper, we propose a new MCE algorithm, called as\(BK_{rcd}\), to improve the efficiency of MCE in a dense degeneracy neighborhood by recursively conducting core decomposition in it. Contrary to\(BK_{pivot}\),\(BK_{rcd}\) is a top-to-down approach, that repeatedly chooses and “removes” the vertex with the smallest degree until a clique is reached. We further integrate\(BK_{rcd}\) into\(MCE_{degeneracy}\) to form a hybrid approach named as\(MCE_{degeneracy}^{hybrid}\), that chooses\(BK_{rcd}\) or\(BK_{pivot}\) adaptively according to the structural properties of the degeneracy neighborhoods. Experimental results conducted in real-world graphs show that\(MCE_{degeneracy}^{hybrid}\) achieves high overall performance improvements on the graphs. For example,\(MCE_{degeneracy}^{hybrid}\) achieves 1.34\(\times \) to 2.97\(\times \) speedups over\(MCE_{degeneracy}\) in web graphs taken in our experiments.
This is a preview of subscription content,log in via an institution to check access.
Access this chapter
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
- Chapter
- JPY 3498
- Price includes VAT (Japan)
- eBook
- JPY 11210
- Price includes VAT (Japan)
- Softcover Book
- JPY 14013
- Price includes VAT (Japan)
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abu-khzam, F., Baldwin, N., Langston, M., Samatova, N.: On the relative efficiency of maximal clique enumeration algorithms, with application to high-throughput computational biology. In: International Conference on Research Trends in Science and Technology, pp. 1–10 (2005)
Alduaiji, N., Datta, A., Li, J.: Influence propagation model for clique-based community detection in social networks. IEEE Trans. Comput. Soc. Syst.5(2), 563–575 (2018)
Bacsó, G., Gravier, S., Gyárfás, A., Preissmann, M., Sebo, A.: Coloring the maximal cliques of graphs. SIAM J. Discret. Math.17(3), 361–376 (2004)
Bailey, P., Craswell, N., Hawking, D.: Engineering a multi-purpose test collection for Web retrieval experiments. Inf. Process. Manag.39(6), 853–871 (2003)
Batagelj, V., Zaversnik, M.: An O(m) algorithm for cores decomposition of networks. Adv. Data Anal. Classif.5(2), 129–145 (2011)
Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM16(9), 575–577 (1973)
Chen, Q., Fang, C., Wang, Z., Suo, B., Li, Z., Ives, Z.G.: Parallelizing maximal clique enumeration over graph data. In: DASFAA, pp. 249–264 (2016)
Cheng, J., Zhu, L., Ke, Y., Chu, S.: Fast algorithms for maximal clique enumeration with limited memory. In: KDD, pp. 1240–1248 (2012)
Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput.14(1), 210–223 (1985)
Conte, A., Virgilio, R.D., Maccioni, A., Patrignani, M., Torlone, R.: Finding all maximal cliques in very large social networks. In: EDBT, pp. 173–184 (2016)
Eppstein, D., Löffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: ISAAC, pp. 403–414 (2010)
Eppstein, D., Strash, D.: Listing all maximal cliques in large sparse real-world graphs. In: SEA, pp. 364–375 (2011)
Leskovec, J., Krevl, A.: SNAP datasets: Stanford large network dataset collection (2014).http://snap.stanford.edu/data
Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math.3(1), 23–28 (1965)
Mukherjee, A.P., Xu, P., Tirthapura, S.: Enumeration of maximal cliques from an uncertain graph. IEEE Trans. Knowl. Data Eng.29(3), 543–555 (2017)
Palla, G., Derényi, I., Farkas, I.J., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature435, 814–818 (2005)
Strash, D.: Quick cliques: quickly compute all maximal cliques in sparse graphs (2014).https://github.com/darrenstrash/quick-cliques
Sun, S., Wang, Y., Liao, W., Wang, W.: Mining maximal cliques on dynamic graphs efficiently by local strategies. In: ICDE, pp. 115–118 (2017)
Tomita, E., Tanaka, A., Takahashi, H.: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci.363(1), 28–42 (2006)
Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput.6(3), 505–517 (1977)
Acknowledgements
This paper is supported by National Key Research and Development Program of China under grant No. 2018YFB1003500, National Natural Science Foundation of China under grant No. 61825202,61832006, and the “Fundamental Research Funds for the Central Universities of China” under grant No. 2017KFYXJJ066.
Author information
Authors and Affiliations
Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China
Yinuo Li, Zhiyuan Shao, Xiaofei Liao & Hai Jin
Institute of Intelligent Computing, School of Computer Science and Technology, Shandong University, Qingdao, China
Dongxiao Yu
- Yinuo Li
You can also search for this author inPubMed Google Scholar
- Zhiyuan Shao
You can also search for this author inPubMed Google Scholar
- Dongxiao Yu
You can also search for this author inPubMed Google Scholar
- Xiaofei Liao
You can also search for this author inPubMed Google Scholar
- Hai Jin
You can also search for this author inPubMed Google Scholar
Corresponding authors
Correspondence toYinuo Li orZhiyuan Shao.
Editor information
Editors and Affiliations
Tsinghua University, Beijing, China
Guoliang Li
Duke University, Durham, NC, USA
Jun Yang
University of Porto, Porto, Portugal
Joao Gama
Chiang Mai University, Chiang Mai, Thailand
Juggapong Natwichai
Beihang University, Beijing, China
Yongxin Tong
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Li, Y., Shao, Z., Yu, D., Liao, X., Jin, H. (2019). Fast Maximal Clique Enumeration for Real-World Graphs. In: Li, G., Yang, J., Gama, J., Natwichai, J., Tong, Y. (eds) Database Systems for Advanced Applications. DASFAA 2019. Lecture Notes in Computer Science(), vol 11446. Springer, Cham. https://doi.org/10.1007/978-3-030-18576-3_38
Download citation
Published:
Publisher Name:Springer, Cham
Print ISBN:978-3-030-18575-6
Online ISBN:978-3-030-18576-3
eBook Packages:Computer ScienceComputer Science (R0)
Share this paper
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative