Efficient Exact Minimum k-Core Search in Real-World Graphs
Authors: 
Qifan Zhang, Shengxin LiuAuthors Info & Claims
Qifan Zhang, Shengxin LiuAuthors Info & ClaimsPages 3391 - 3401
Abstract
The k-core, which refers to the induced subgraph with a minimum degree of at least k, is widely used in cohesive subgraph discovery and has various applications. However, the k-core in real-world graphs tends to be extremely large, which hinders its effectiveness in practical applications. This challenge has motivated researchers to explore a variant of the k-core problem known as the minimum k-core search problem. This problem has been proven to be NP-Hard, and most of the existing studies naturally either deal with approximate solutions or suffer from inefficiency in practice. In this paper, we focus on designing efficient exact algorithms for the minimum k-core search problem. In particular, we develop an iterative-based framework that decomposes an instance of the minimum k-core search problem into a list of problem instances on another well-structured graph pattern. Based on this framework, we propose an iterative-based branch-and-bound algorithm, namely IBB, with additional pruning and reduction techniques. We show that, with a n-vertex graph, IBB runs in cn nO(1) time for some c < 2, achieving better theoretical performance than the trivial bound of 2n nO(1). Finally, our experiments on real-world graphs demonstrate that IBB is up to three orders of magnitude faster than the state-of-the-art algorithms on real-world datasets.
References
[1]
Md Altaf-Ul-Amine, Kensaku Nishikata, Toshihiro Korna, Teppei Miyasato, Yoko Shinbo, Md Arifuzzaman, Chieko Wada, Maki Maeda, Taku Oshima, Hirotada Mori, et al. 2003. Prediction of protein functions based on k-cores of protein-protein interaction networks and amino acid sequences. Genome Informatics, Vol. 14 (2003), 498--499.
[2]
Gary D Bader and Christopher WV Hogue. 2003. An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics, Vol. 4, 1 (2003), 1--27.
[3]
Balabhaskar Balasundaram, Sergiy Butenko, and Illya V. Hicks. 2011. Clique Relaxations in Social Network Analysis: The Maximum k-Plex Problem. Operations Research, Vol. 59, 1 (2011), 133--142.
[4]
Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and effective community search. Data Mining and Knowledge Discovery, Vol. 29, 5 (2015), 1406--1433.
[5]
Vladimir Batagelj and Matjaz Zaversnik. 2003. An $O(m)$ algorithm for cores decomposition of networks. arXiv preprint cs/0310049 (2003).
[6]
Vladimir Batagelj and Matjavz Zavervs nik. 2011. Fast algorithms for determining (generalized) core groups in social networks. Advances in Data Analysis and Classification, Vol. 5, 2 (2011), 129--145.
[7]
Francesco Bonchi, Francesco Gullo, Andreas Kaltenbrunner, and Yana Volkovich. 2014. Core decomposition of uncertain graphs. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). 1316--1325.
[8]
Francesco Bonchi, Arijit Khan, and Lorenzo Severini. 2019. Distance-generalized core decomposition. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 1006--1023.
[9]
Shaowei Cai and Jinkun Lin. 2016. Fast Solving Maximum Weight Clique Problem in Massive Graphs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 568--574.
[10]
Lijun Chang and Lu Qin. 2019. Cohesive subgraph computation over large sparse graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 2068--2071.
[11]
Lijun Chang, Mouyi Xu, and Darren Strash. 2022. Efficient maximum k-plex computation over large sparse graphs. Proceedings of the VLDB Endowment, Vol. 16, 2 (2022), 127--139.
[12]
Peilin Chen, Hai Wan, Shaowei Cai, Weilin Luo, and Jia Li. 2019. Combining reinforcement learning and configuration checking for maximum k-plex problem. CoRR, Vol. abs/1906.02578 (2019).
[13]
James Cheng, Yiping Ke, Shumo Chu, and M Tamer Özsu. 2011. Efficient core decomposition in massive networks. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 51--62.
[14]
Rajesh Chitnis, Fedor V Fomin, and Petr A Golovach. 2016. Parameterized complexity of the anchored k-core problem for directed graphs. Information and Computation, Vol. 247 (2016), 11--22.
[15]
Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National Security Agency Technical Report, Vol. 16, 3.1 (2008).
[16]
Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local search of communities in large graphs. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 991--1002.
[17]
Danhao Ding, Hui Li, Zhipeng Huang, and Nikos Mamoulis. 2017. Efficient fault-tolerant group recommendation using alpha-beta-core. In Proceedings of the ACM on Conference on Information and Knowledge Management (CIKM). 2047--2050.
[18]
Yi Fan, Nan Li, Chengqian Li, Zongjie Ma, Longin Jan Latecki, and Kaile Su. 2017. Restart and random walk in local search for maximum vertex weight cliques with evaluations in clustering aggregation. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 622--630.
[19]
Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020a. A survey of community search over big graphs. The VLDB Journal, Vol. 29 (2020), 353--392.
[20]
Yixiang Fang, Kai Wang, Xuemin Lin, and Wenjie Zhang. 2022. Cohesive subgraph search over large heterogeneous information networks. Springer.
[21]
Yixiang Fang, Yixing Yang, Wenjie Zhang, Xuemin Lin, and Xin Cao. 2020b. Effective and efficient community search over large heterogeneous information networks. Proceedings of the VLDB Endowment, Vol. 13, 6 (2020), 854--867.
[22]
Jian Gao, Jiejiang Chen, Minghao Yin, Rong Chen, and Yiyuan Wang. 2018. An exact algorithm for maximum k-plexes in massive graphs. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1449--1455.
[23]
Bishwamittra Ghosh, Mohammed Eunus Ali, Farhana M Choudhury, Sajid Hasan Apon, Timos Sellis, and Jianxin Li. 2018. The flexible socio spatial group queries. Proceedings of the VLDB Endowment, Vol. 12, 2 (2018), 99--111.
[24]
Emmanuel Hebrard and George Katsirelos. 2018. Conflict directed clause learning for maximum weighted clique problem. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1316--1323.
[25]
William Jack, Adam Ray, and Tavneet Suri. 2013. Transaction networks: Evidence from mobile money in Kenya. American Economic Review, Vol. 103, 3 (2013), 356--361.
[26]
Xun Jian, Yue Wang, and Lei Chen. 2020. Effective and efficient relational community detection and search in large dynamic heterogeneous information networks. Proceedings of the VLDB Endowment, Vol. 13, 10 (2020), 1723--1736.
[27]
Hua Jiang, Chu-Min Li, Yanli Liu, and Felip Manyà. 2018. A two-stage MaxSAT reasoning approach for the maximum weight clique problem. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 1338--1346.
[28]
Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, and Zhang-Hua Fu. 2021. A new upper bound based on vertex partitioning for the Maximum k-plex Problem. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 1689--1696.
[29]
Franziskos Kyriakopoulos, Stefan Thurner, Claus Puhr, and Stefan W Schmitz. 2009. Network and eigenvalue analysis of financial transaction networks. The European Physical Journal B, Vol. 71 (2009), 523--531.
[30]
Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A survey of algorithms for dense subgraph discovery. Managing and Mining Graph Data (2010), 303--336.
[31]
Conggai Li, Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2020. Efficient progressive minimum k-core search. Proceedings of the VLDB Endowment, Vol. 13, 3 (2020), 362--375.
[32]
Rong-Hua Li, Jiao Su, Lu Qin, Jeffrey Xu Yu, and Qiangqiang Dai. 2018. Persistent community search in temporal networks. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 797--808.
[33]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2020b. Efficient (?, ?)-core computation in bipartite graphs. The VLDB Journal, Vol. 29, 5 (2020), 1075--1099.
[34]
Boge Liu, Fan Zhang, Chen Zhang, Wenjie Zhang, and Xuemin Lin. 2019. Corecube: Core decomposition in multilayer graphs. In Proceedings of the Web Information Systems Engineering (WISE). 694--710.
[35]
Boge Liu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2021. Efficient community search with size constraint. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 97--108.
[36]
Jingxin Liu, Chang Xu, Chang Yin, Weiqiang Wu, and You Song. 2020a. k-core based temporal graph convolutional network for dynamic graphs. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 8 (2020), 3841--3853.
[37]
Qing Liu, Minjun Zhao, Xin Huang, Jianliang Xu, and Yunjun Gao. 2020c. Truss-based community search over large directed graphs. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 2183--2197.
[38]
Junjie Luo, Hendrik Molter, and Ondrej Suchý. 2018. A parameterized complexity view on collapsing k-cores. In Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC). 7:1--7:14.
[39]
Wensheng Luo, Kenli Li, Xu Zhou, Yunjun Gao, and Keqin Li. 2022. Maximum biplex search over bipartite graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 898--910.
[40]
Yu-Liang Ma, Ye Yuan, Fei-Da Zhu, Guo-Ren Wang, Jing Xiao, and Jian-Zong Wang. 2019. Who should be invited to my party: A size-constrained k-core problem in social networks. Journal of Computer Science and Technology, Vol. 34 (2019), 170--184.
[41]
Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: Theory, algorithms and applications. The VLDB Journal, Vol. 29 (2020), 61--92.
[42]
Derek Mikesell and Illya V Hicks. 2022. Minimum k-cores and the k-core polytope. Networks, Vol. 80, 1 (2022), 93--108.
[43]
David Peleg, Ignasi Sau, and Mordechai Shalom. 2013. On approximating the d-girth of a graph. Discrete Applied Mathematics, Vol. 161, 16--17 (2013), 2587--2596.
[44]
Stephen B Seidman. 1983. Network structure and minimum degree. Social Networks, Vol. 5, 3 (1983), 269--287.
[45]
Jieying She, Yongxin Tong, Lei Chen, and Tianshu Song. 2017. Feedback-aware social event-participant arrangement. In Proceedings of the ACM International Conference on Management of Data (SIGMOD). 851--865.
[46]
Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In Proceedings of the ACM International Conference on Knowledge Discovery and Data Mining (KDD). 939--948.
[47]
Panagiotis Symeonidis, Eleftherios Tiakas, and Yannis Manolopoulos. 2011. Product recommendation and rating prediction based on multi-modal social networks. In Proceedings of the ACM conference on Recommender systems (RecSys). 61--68.
[48]
Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, Lu Qin, and Yuting Zhang. 2021. Efficient and effective community search on large-scale bipartite graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). 85--96.
[49]
Mingyu Xiao, Weibo Lin, Yuanshun Dai, and Yifeng Zeng. 2017. A fast algorithm to compute maximum k-plexes in social network analysis. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 919--925.
[50]
Kai Yao and Lijun Chang. 2021. Efficient size-bounded community search over large networks. Proceedings of the VLDB Endowment, Vol. 14, 8 (2021), 1441--1453.
[51]
Fan Zhang, Haicheng Guo, Dian Ouyang, Shiyu Yang, Xuemin Lin, and Zhihong Tian. 2023. Size-constrained community search on large networks: An effective and efficient solution. IEEE Transactions on Knowledge and Data Engineering (2023).
[52]
Fan Zhang, Ying Zhang, Lu Qin, Wenjie Zhang, and Xuemin Lin. 2017. Finding Critical Users for Social Network Engagement: The Collapsed k-Core Problem. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 245--251.
[53]
Hanpeng Zhang, Zhaohua Wang, Shengjun Chen, and Chengqi Guo. 2019b. Product recommendation in online social networking communities: An empirical study of antecedents and a mediator. Information & Management, Vol. 56, 2 (2019), 185--195.
[54]
Ying Zhang, Lu Qin, Fan Zhang, and Wenjie Zhang. 2019a. Hierarchical decomposition of big graphs. In Proceedings of the IEEE International Conference on Data Engineering (ICDE). IEEE, 2064--2067.
[55]
Yi Zhou, Shan Hu, Mingyu Xiao, and Zhang-Hua Fu. 2021. Improving maximum k-plex solver via second-order reduction and graph color bounding. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 12453--12460.
[56]
Zhongxin Zhou, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Chen Chen. 2019. K-core maximization: An edge addition approach. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). 4867--4873.
Index Terms
- Efficient Exact Minimum k-Core Search in Real-World Graphs
Recommendations
Hamiltonian claw-free graphs involving minimum degrees
Favaron and Fraisse proved that any 3-connected claw-free graph H with order n and minimum degree @d(H)>=n+3810 is hamiltonian [O. Favaron and P. Fraisse, Hamiltonicity and minimum degree in 3-connected claw-free graphs, J. Combin. Theory B 82 (2001) ...
Patterns and anomalies in k-cores of real-world graphs with applications
How do the k-core structures of real-world graphs look like__ __ What are the common patterns and the anomalies__ __ How can we exploit them for applications__ __ A k-core is the maximal subgraph in which all vertices have degree at least k. This ...
Triangle-free subcubic graphs with minimum bipartite density
A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is max{@e(H)/@e(G):H is a bipartite subgraph of G}, where @e(H) and @e(G) denote the numbers of edges in H and G, respectively. It is an NP-hard problem to ...
Comments
Information & Contributors
Information
Published In
October 2023
5508 pages
ISBN:9798400701245
DOI:10.1145/3583780
- General Chairs:
- Ingo Frommholz,
- Frank Hopfgartner,
- Mark Lee,
- Michael Oakes,
- Program Chairs:
- Mounia Lalmas,
- Min Zhang,
- Rodrygo Santos
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- National Natural Science Foundation of China
- Guangdong Basic and Applied Basic Research Foundation
- Shenzhen Science and Technology Program
Conference
CIKM '23: The 32nd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2023
Birmingham, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 181Total Downloads
- Downloads (Last 12 months)106
- Downloads (Last 6 weeks)9
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in