A divisive spectral method for network community detection

Abstract

Community detection is a fundamental problem in the domain of complex-network analysis. It has received great attention, and many community detection methods have been proposed in the last decade. In this paper, we propose a divisive spectral method for identifying community structures from networks, which utilizes a sparsification operation to pre-process the networks first, and then uses a repeated bisection spectral algorithm to partition the networks into communities. The sparsification operation makes the community boundaries more clearer and more sharper, so that the repeated spectral bisection algorithm extract high-quality community structures accurately from the sparsified networks. Experiments show that the combination of network sparsification and spectral bisection algorithm is highly successful, the proposed method is more effective in detecting community structures from networks than the others.

23pages, 10 figures, and 2 tables

References in corpus (7)

• Finding community structure in networks using the eigenvectors of matrices
• Cooperative Game Theory Approaches for Network Partitioning
• Benchmark graphs for testing community detection algorithms
• Resolution limit in community detection
• Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
• Spectral methods for the detection of network community structure: a comparative analysis
• Covariance, correlation matrix and the multi-scale community structure of networks

Cited by in corpus (2)

• Identifying multi-scale communities in networks by asymptotic surprise
• A Distributed Algorithm for Overlapped Community Detection in Large-Scale Networks