Overlapping community detection in networks via sparse spectral decomposition
arXiv:2009.10641 · doi:10.1007/s13171-021-00245-4
Abstract
We consider the problem of estimating overlapping community memberships in a network, where each node can belong to multiple communities. More than a few communities per node are difficult to both estimate and interpret, so we focus on sparse node membership vectors. Our algorithm is based on sparse principal subspace estimation with iterative thresholding. The method is computationally efficient, with a computational cost equivalent to estimating the leading eigenvectors of the adjacency matrix, and does not require an additional clustering step, unlike spectral clustering methods. We show that a fixed point of the algorithm corresponds to correct node memberships under a version of the stochastic block model. The methods are evaluated empirically on simulated and real-world networks, showing good statistical performance and computational efficiency.
References in corpus (24)
- Community structure in social and biological networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- Stochastic blockmodels and community structure in networks
- Detecting the overlapping and hierarchical community structure of complex networks
- Finding statistically significant communities in networks
- Overlapping Community Detection in Networks: the State of the Art and Comparative Study
- Finding overlapping communities in networks by label propagation
- Mixed membership stochastic blockmodels
- The phase transition in inhomogeneous random graphs
- Spectral clustering and the high-dimensional stochastic blockmodel
- An efficient and principled method for detecting communities in networks
- Sparse principal component analysis and iterative thresholding
- Consistency of spectral clustering in stochastic block models
- Fast community detection by SCORE
- Overlapping stochastic block models with application to the French political blogosphere
- Coauthorship and Citation Networks for Statisticians
- Minimax sparse principal subspace estimation in high dimensions
- Estimating the number of communities in networks by spectral methods
- Mixed Membership Estimation for Social Networks
- Overlapping Clustering Models, and One (class) SVM to Bind Them All
- Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
- On Mixed Memberships and Symmetric Nonnegative Matrix Factorizations
- Simultaneous prediction and community detection for networks with application to neuroimaging