Effective K-Vertex connected component detection in large-scale networks
Conference Proceeding Article
Finding components with high connectivity is an important problem in component detection with a wide range of applications, e.g., social network analysis, web-page research and bioinformatics. In particular, k-edge connected component (k-ECC) has recently been extensively studied to discover disjoint components. Yet many real applications present 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 therefore allows overlapping between components. To find k-VCCs, a top-down framework is first developed to find the exact k-VCCs. To further reduce the high computational cost for input networks of large sizes, a bottom-up framework is then proposed. Instead of using the structure of the entire network, it locally identifies the seed subgraphs, and obtains the heuristic k-VCCs by expanding and merging these seed subgraphs. Comprehensive experimental results on large real and synthetic networks demonstrate the efficiency and effectiveness of our approaches.
Databases and Information Systems | OS and Networks
Data Management and Analytics
Proceedings of The 22nd International Conference on Database Systems for Advanced Applications: Suzhou, China, 2017 March 27-30
City or Country
LI, Yuan; ZHAO, Yuha; WANG, Wang; ZHU, Feida; WU, Yubao; and SHI, Shenglei.
Effective K-Vertex connected component detection in large-scale networks. (2017). Proceedings of The 22nd International Conference on Database Systems for Advanced Applications: Suzhou, China, 2017 March 27-30. 10178, 404-421. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/3617