Likelihood-based model selection for stochastic block models
Open accessThe DOI matches its Crossref record; 24 of the 24 references it cites were found in a registry or an index.
Abstract
The stochastic block model (SBM) provides a popular framework for modeling community structures in networks. However, more attention has been devoted to problems concerning estimating the latent node labels and the model parameters than the issue of choosing the number of blocks. We consider an approach based on the log likelihood ratio statistic and analyze its asymptotic properties under model misspecification. We show the limiting distribution of the statistic in the case of underfitting is normal and obtain its convergence rate in the case of overfitting. These conclusions remain valid when the average degree grows at a polylog rate. The results enable us to derive the correct order of the penalty term for model complexity and arrive at a likelihood-based model selection criterion that is asymptotically consistent. Our analysis can also be extended to a degree-corrected block model (DCSBM). In practice, the likelihood function can be estimated using more computationally efficient variational methods or consistent label estimation algorithms, allowing the criterion to be applied to large networks.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Modularity and community structure in networks
Newman, M. E. J. (2006) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0601602103 · Cited by 12,256 · cited 1×
“Much research effort has been devoted to the problems of estimating the latent block memberships and model parameters of a SBM, including modularity (Newman, 2006a) and likelihood maximization (Bickel and Chen, 2009; Amini et al., 2013), variational methods (Daudin, Picard and Robin, 2008; Latouche,…”
MethodFinding community structure in networks using the eigenvectors of matrices
Newman, M. E. J. (2006) · Physical Review E · doi:10.1103/physreve.74.036104 · Cited by 4,761 · cited 1×
“We also experimented these methods on the political book network (Newman, 2006b), which consists of 105 books and their edges representing copurchase information from Amazon.”
MethodStochastic blockmodels: First steps
Holland, P. W., Laskey, K. B., & Leinhardt, S. (1983) · Social Networks · doi:10.1016/0378-8733(83)90021-7 · Cited by 2,755 · cited 1×
“The stochastic block model (SBM), proposed by Holland, Laskey and Leinhardt (1983) in social science, is one of the simplest random graph models incorporating community structures.”
MethodThe political blogosphere and the 2004 U.S. election: divided they blog
Adamic, L. A., & Glance, N. (2005) · Proceedings of the 3rd international workshop on Link discovery · doi:10.1145/1134271.1134277 · Cited by 2,619
Learning to Discover Social Circles in Ego Networks
Leskovec, J., & McAuley, J. (2012) · neural information processing systems · Cited by 2,491
Stochastic blockmodels and community structure in networks
Karrer, B., & Newman, M. E. J. (2011) · Physical Review E · doi:10.1103/physreve.83.016107 · Cited by 2,025 · cited 9×
“In practice, this model sometimes oversimplifies the structures of real networks and other variants have been proposed, including the degree-corrected SBM (Karrer and Newman, 2011) relaxing the within-block degree homogeneity constraint and overlapping SBM (Airoldi et al., 2008) allowing a node to be in multiple blocks.”
BackgroundMethodInfluentialMixed membership stochastic blockmodels
Airoldi, E. M., Blei, D. M., Fienberg, S. E., & Xing, E. P. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0705.4485 · Cited by 781
A nonparametric view of network models and Newman–Girvan and other modularities
Bickel, P. J., & Chen, A. (2009) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.0907096106 · Cited by 765 · cited 6×
“However, in practice the number of communities is also likely to grow as a network expands (Choi, Wolfe and Airoldi, 2012), especially when we view block models as histogram approximations for more general models (Bickel and Chen, 2009; Wolfe and Olhede, 2013).”
BackgroundMethodInfluentialSelf-citationDecelle, A., Krzakala, F., Moore, C., & Zdeborová, L. (2011) · Physical Review E · doi:10.1103/physreve.84.066106 · Cited by 747 · cited 1×
“…likelihood maximization (Bickel and Chen, 2009; Amini et al., 2013), variational methods (Daudin, Picard and Robin, 2008; Latouche, Birmele and Ambroise, 2012), spectral clustering (Rohe, Chatterjee and Yu, 2011; Fishkind et al., 2013), belief propagation (Decelle et al., 2011) to name but a few.”
MethodSpectral clustering and the high-dimensional stochastic blockmodel
Rohe, K., Chatterjee, S., & Yu, B. (2011) · The Annals of Statistics · doi:10.1214/11-aos887 · Cited by 535
Cited by
Jusup, M., Holme, P., Kanazawa, K., Takayasu, M., Romić, I., Wang, Z., Geček, S., Lipić, T., Podobnik, B., Wang, L., et al. (2022) · Physics Reports · doi:10.1016/j.physrep.2021.10.005 · Cited by 643
Metadata
- Authors
- Wang, Y. X. R., & Bickel, P. J.
- Venue
- The Annals of Statistics
- Publisher
- Institute of Mathematical Statistics
- Published
- 2017-04-01
- Volume
- 45
- Issue
- 2
- Pages
- 500-528
- ISSN
- 0090-5364 (ISSN-L)
- OpenAlex
- W1467346733
- Cited by
- 174
- References
- 24
- FWCI
- 9.27
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Likelihood-based model selection for stochastic block models. https://app.cochat.ai/papers/10.1214/16-aos1457
- The paper
- Wang, Y. X. R., & Bickel, P. J. (2017). Likelihood-based model selection for stochastic block models. The Annals of Statistics. https://doi.org/10.1214/16-aos1457
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.