Estimating the number of communities in networks by spectral methods

Abstract

Community detection is a fundamental problem in network analysis with many methods available to estimate communities. Most of these methods assume that the number of communities is known, which is often not the case in practice. We study a simple and very fast method for estimating the number of communities based on the spectral properties of certain graph operators, such as the non-backtracking matrix and the Bethe Hessian matrix. We show that the method performs well under several models and a wide range of parameters, and is guaranteed to be consistent under several asymptotic regimes. We compare this method to several existing methods for estimating the number of communities and show that it is both more accurate and more computationally efficient.

References in corpus (6)

• Modularity and community structure in 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
• Parsimonious module inference in large networks
• Network cross-validation by edge sampling

Cited by in corpus (24)

• Evaluating Overfit and Underfit in Models of Network Community Structure
• A Survey on Theoretical Advances of Community Detection in Networks
• Optimal hypothesis testing for stochastic block models with growing degrees
• Hierarchical community structure in networks
• Determining the Number of Communities in Degree-corrected Stochastic Block Models
• Network cross-validation by edge sampling
• Unified ${\ell }_{2\to \infty }$ Eigenspace Perturbation Theory for Symmetric Random Matrices
• Community detection with nodal information
• General Community Detection with Optimal Recovery Conditions for Multi-relational Sparse Networks with Dependent Layers
• A unified framework for spectral clustering in sparse graphs
• Hierarchical community detection by recursive partitioning
• Voter model on networks partitioned into two cliques of arbitrary sizes
• ALMA: Alternating Minimization Algorithm for Clustering Mixture Multilayer Network
• Covariate Regularized Community Detection in Sparse Graphs
• Universal Rank Inference via Residual Subsampling with Application to Large Networks
• Spectral clustering via adaptive layer aggregation for multi-layer networks
• Linear regression and its inference on noisy network-linked data
• Probabilistic community detection with unknown number of communities
• Hypothesis Testing for Equality of Latent Positions in Random Graphs
• Estimating Graph Dimension with Cross-validated Eigenvalues
• Clustering of Diverse Multiplex Networks
• Strong consistency of Krichevsky-Trofimov estimator for the number of communities in the Stochastic Block Model
• An improved spectral clustering method for community detection under the degree-corrected stochastic blockmodel
• Overlapping community detection in networks via sparse spectral decomposition