Efficient size-prescribed k-core search
November 2023
Pages 271 - 275
Abstract
k-core is a subgraph where every node has at least k neighbors within the subgraph. The k-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding k-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed k-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the TSizeKcore-BU and the TSizeKcore-TD, to identify cohesive subgraphs that satisfy both the k-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The TSizeKcore-BU algorithm proves to be highly efficient in finding size-prescribed k-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the TSizeKcore-TD algorithm is better suited for small datasets where running time is less critical.
References
[1]
J. I. Alvarez-Hamelin, L. Dall'Asta, A. Barrat, and A. Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems 18, 2005.
[2]
Omid Amini, Ignasi Sau, and Saket Saurabh. 2012. Parameterized complexity of finding small degree-constrained subgraphs. Journal of Discrete Algorithms 10 (2012), 70--83.
[3]
Nicola Barbieri, Francesco Bonchi, Edoardo Galimberti, and Francesco Gullo. 2015. Efficient and effective community search. Data mining and knowledge discovery 29 (2015), 1406--1433.
[4]
Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local search of communities in large graphs. In Proceedings of the 2014 ACM SIGMOD international conference on Management of data. 991--1002.
[5]
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 (2020).
[6]
Yu-Liang Ma, Ye Yuan, Fei-Da Zhu, Guo-Ren Wang, Jing Xiao, and Jian-Zong Wang. 2019a. Who should be invited to my party: A size-constrained k- core problem in social networks. Journal of Computer Science and Technology 34 (2019), 170--184.
[7]
David W Matula and Leland L Beck. 1983. Smallest-last ordering and clustering and graph coloring algorithms. Journal of the ACM (JACM) 30, 3 (1983), 417--427.
[8]
Aua Md., H. Mori, S. Kanaya, K. Nishikata, T. Korna, T. Miyasato, Y. Shinbo, A. Md., C. Wada, and M. Maeda. 2011. Prediction of Protein Functions Based on K-Cores of Protein-Protein Interaction Networks and Amino Acid Sequences. Genome Informatics 14 (2011)
[9]
Mikail Rubinov and Olaf Sporns. 2010. Complex network measures of brain connectivity: uses and interpretations. NEUROIMAGE 3 (2010).
[10]
Mauro Sozio and Aristides Gionis. 2010. The community-search problem and how to plan a successful cocktail party. KDD, 939--948.
[11]
Douglas Brent West et al. 2001. Introduction to graph theory. Vol. 2. Prentice hall Upper Saddle River.
[12]
Stefan Wuchty and Eivind Almaas. 2005. Peeling the yeast protein network. Proteomics 5, 2 (2005), 444--449.
[13]
K. Yao and L. Chang. 2021. Efficient size-bounded community search over large networks. In Very Large Data Bases.
[14]
Batagelj V, Zaversnik M. An o (m) algorithm for cores decomposition of networks[J]. arXiv preprint cs/0310049, 2003.
[15]
Luo X, Andrews M, Song Y, et al. Group-buying deal popularity[J]. Journal of Marketing, 2014, 78(2): 20--33.
[16]
Boutsis I, Karanikolaou S, Kalogeraki V. Personalized event recommendations using social networks[C]//2015 16th IEEE International Conference on Mobile Data Management. IEEE, 2015, 1: 84--93.
[17]
Downey R G, Fellows M R. Fixed-parameter tractability and completeness II: On completeness for W [1][J]. Theoretical Computer Science, 1995, 141(1--2): 109--131.
[18]
Hastad J. Clique is hard to approximate within n/sup 1-/spl epsiv[C]//Proceedings of 37th Conference on Foundations of Computer Science. IEEE, 1996: 627--636.
Index Terms
- Efficient size-prescribed k-core search
Index terms have been assigned to the content through auto-classification.
Recommendations
Efficient Exact Minimum k-Core Search in Real-World Graphs
CIKM '23: Proceedings of the 32nd ACM International Conference on Information and Knowledge ManagementThe 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 ...
Incremental k-core decomposition: algorithms and evaluation
A k-core of a graph is a maximal connected subgraph in which every vertex is connected to at least k vertices in the subgraph. k-core decomposition is often used in large-scale network analysis, such as community detection, protein function prediction, ...
Induced subgraphs of prescribed size
A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let q(G) denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open problem of Erdõs and McKay we show that every graph G on n vertices for ...
Comments
Information & Contributors
Information
Published In
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: 15 March 2024
Check for updates
Author Tags
Qualifiers
- Short-paper
Funding Sources
Conference
ASONAM '23
Sponsor:
ASONAM '23: International Conference on Advances in Social Networks Analysis and Mining
November 6 - 9, 2023
Kusadasi, Turkiye
Acceptance Rates
ASONAM '23 Paper Acceptance Rate 53 of 145 submissions, 37%;
Overall Acceptance Rate 116 of 549 submissions, 21%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 22Total Downloads
- Downloads (Last 12 months)22
- Downloads (Last 6 weeks)2
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in