A divisive spectral method for network community detection
arXiv:1506.08354 · doi:10.1088/1742-5468/2016/03/033403
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.
arXiv comment23pages, 10 figures, and 2 tables
References in corpus (19)
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Hierarchical organization of modularity in metabolic networks
- Functional cartography of complex metabolic networks
- Benchmark graphs for testing community detection algorithms
- Resolution limit in community detection
- Synchronization reveals topological scales in complex networks
- Spectral redemption: clustering sparse networks
- Spectral methods for network community detection and graph partitioning
- Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems
- Detecting Network Communities: a new systematic and efficient algorithm
- Detecting communities in large networks
- Pseudo-likelihood methods for community detection in large sparse networks
- Spectral methods for the detection of network community structure: a comparative analysis
- Uncovering the community structure associated with the diffusion dynamics of networks
- Covariance, correlation matrix and the multi-scale community structure of networks