A goodness-of-fit test for stochastic block models
arXiv:1412.4857 · doi:10.1214/15-AOS1370
Abstract
The stochastic block model is a popular tool for studying community structures in network data. We develop a goodness-of-fit test for the stochastic block model. The test statistic is based on the largest singular value of a residual matrix obtained by subtracting the estimated block mean effect from the adjacency matrix. Asymptotic null distribution is obtained using recent advances in random matrix theory. The test is proved to have full power against alternative models with finer structures. These results naturally lead to a consistent sequential testing estimate of the number of communities.
arXiv commentPublished at http://dx.doi.org/10.1214/15-AOS1370 in the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)
References in corpus (17)
- Finding and evaluating community structure in networks
- Modularity and community structure in networks
- Stochastic blockmodels and community structure in networks
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Spectral redemption: clustering sparse networks
- Matrix estimation by Universal Singular Value Thresholding
- Consistency of spectral clustering in stochastic block models
- Fast community detection by SCORE
- Consistency of community detection in networks under degree-corrected stochastic block models
- Spectral Statistics of Erd{\H o}s-Rényi Graphs II: Eigenvalue Spacing and the Extreme Eigenvalues
- Spectral statistics of Erdős-Rényi graphs I: Local semicircle law
- Community extraction for social networks
- Model Selection for Degree-corrected Block Models
- A Necessary and Sufficient Condition for Edge Universality of Wigner matrices
- A Tensor Approach to Learning Mixed Membership Community Models
- A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models
- Isotropic Local Laws for Sample Covariance and Generalized Wigner Matrices
Cited by in corpus (10)
- A Survey on Theoretical Advances of Community Detection in Networks
- Two-sample Hypothesis Testing for Inhomogeneous Random Graphs
- A useful criterion on studying consistent estimation in community detection
- Correcting a Nonparametric Two-sample Graph Hypothesis Test for Graphs with Different Numbers of Vertices with Applications to Connectomics
- The Asymptotic Distribution of Modularity in Weighted Signed Networks
- Estimating the number of communities in weighted networks
- Sequential locality of graphs and its hypothesis testing
- Spectral goodness-of-fit tests for complete and partial network data
- Consistent model selection for the Degree Corrected Stochastic Blockmodel
- A Unified Framework for Community Detection and Model Selection in Blockmodels