Publication Type
Journal Article
Version
acceptedVersion
Publication Date
3-2020
Abstract
In many real life network-based applications such as social relation analysis, Web analysis, collaborative network, road network and bioinformatics, the discovery of components with high connectivity is an important problem. In particular, k-edge connected component (k-ECC) has recently been extensively studied to discover disjoint components. Yet many real scenarios present more needs and challenges for overlapping components. In this paper, we propose a k-vertex connected component (k-VCC) model, which is much more cohesive, and thus supports overlapping between components very well. To discover k-VCCs, we propose three frameworks including top-down, bottom-up and hybrid frameworks. The top-down framework is first developed to find the exact k-VCCs by dividing the whole network. To further reduce the high computational cost for input networks of large sizes, a bottom-up framework is then proposed to locally identify the seed subgraphs, and obtain the heuristic k-VCCs by expanding and merging these seed subgraphs. Finally, the hybrid framework takes advantages of the above two frameworks. It exploits the results of bottom-up framework to construct the well-designed mixed graph and then discover the exact k-VCCs by contracting the mixed graph in a top-down way. Because the size of mixed graph is smaller than the original network, the hybrid framework runs much faster than the top-down framework. Comprehensive experimental are conducted on large real and synthetic networks and demonstrate the efficiency and effectiveness of the proposed exact and heuristic approaches.
Keywords
Component detection, K-vertex connected component (k-VCC), Large network
Discipline
Databases and Information Systems | Theory and Algorithms
Research Areas
Data Science and Engineering
Publication
World Wide Web
Volume
23
Issue
2
First Page
799
Last Page
830
ISSN
1386-145X
Identifier
10.1007/s11280-019-00725-6
Publisher
Springer
Embargo Period
5-30-2021
Citation
YUAN, Li; WANG, Guoren; ZHAO, Yuhai; and ZHU, Feida.
Towards k-vertex connected component discovery from large networks. (2020). World Wide Web. 23, (2), 799-830.
Available at: https://ink.library.smu.edu.sg/sis_research/5974
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
https://doi.org/10.1007/s11280-019-00725-6