Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

3-2017

Abstract

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.

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

Database Systems for Advanced Applications: 22nd International Conference, DASFAA 2017, Suzhou, China, March 27-30: Proceedings

Volume

10178

First Page

404

Last Page

421

ISBN

9783319556994

Identifier

10.1007/978-3-319-55699-4_25

Publisher

Springer

City or Country

Cham

Copyright Owner and License

Authors

Additional URL

https://doi.org/10.1007/978-3-319-55699-4_25

Download

Share

COinS