A goodness-of-fit test for stochastic block models

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.

Published 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 (4)

• Modularity and community structure in networks
• Stochastic blockmodels and community structure in networks
• Consistency of spectral clustering in stochastic block models
• A Generic Sample Splitting Approach for Refined Community Recovery in Stochastic Block Models

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