Multiway spectral community detection in networks
arXiv:1507.05108 · doi:10.1103/PhysRevE.92.052808
Abstract
One of the most widely used methods for community detection in networks is the maximization of the quality function known as modularity. Of the many maximization techniques that have been used in this context, some of the most conceptually attractive are the spectral methods, which are based on the eigenvectors of the modularity matrix. Spectral algorithms have, however, been limited by and large to the division of networks into only two or three communities, with divisions into more than three being achieved by repeated two-way division. Here we present a spectral algorithm that can directly divide a network into any number of communities. The algorithm makes use of a mapping from modularity maximization to a vector partitioning problem, combined with a fast heuristic for vector partitioning. We compare the performance of this spectral algorithm with previous approaches and find it to give superior results, particularly in cases where community sizes are unbalanced. We also give demonstrative applications of the algorithm to two real-world networks and find that it produces results in good agreement with expectations for the networks studied.
arXiv comment10 pages, 5 figures
References in corpus (19)
- Fast unfolding of communities in large networks
- Community structure in social and biological networks
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Community detection in graphs
- Finding community structure in very large networks
- Fast algorithm for detecting community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Random graphs with arbitrary degree distributions and their applications
- Comparing community structure identification
- Stochastic blockmodels and community structure in networks
- Community detection in complex networks using Extremal Optimization
- The performance of modularity maximization in practical contexts
- Modularity from Fluctuations in Random Graphs and Complex Networks
- Spectral redemption: clustering sparse networks
- Spectral methods for network community detection and graph partitioning
- Phase transition in the detection of modules in sparse networks
- Graph spectra and the detectability of community structure in networks
- Spectral tripartitioning of networks
Cited by in corpus (7)
- Graph Unlearning
- Network community-based model reduction for vortical flows
- Community detection in networks via nonlinear modularity eigenvectors
- Geometric Multiscale Community Detection: Markov Stability and Vector Partitioning
- An ensemble based on a bi-objective evolutionary spectral algorithm for graph clustering
- Communities in C.elegans connectome through the prism of non-backtracking walks
- Correlation Clustering with Low-Rank Matrices