Asymptotic uncertainty quantification for communities in sparse planted bi-section models
Preprint
Abstract
Posterior distributions for community structure in sparse planted bi-section models are shown to achieve exact (resp. almost-exact) recovery, with sharp bounds for the sparsity regimes where edge probabilities decrease as $O(\log(n)/n)$ (resp. $O(1/n)$). Assuming posterior recovery, one may interpret credible sets (resp. enlarged credible sets) as asymptotically consistent confidence sets; the diameters of those credible sets are controlled by the rate of posterior concentration. If credible levels are chosen to grow to one quickly enough, corresponding credible sets can be interpreted as frequentist confidence sets without conditions on posterior concentration. In the regimes with $O(1/n)$ edge sparsity, or when within-community and between-community edge probabilities are very close, credible sets may be enlarged to achieve frequentist asymptotic coverage, also without conditions on posterior concentration.
Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- A likelihood-ratio type test for stochastic block models with bounded degreesJournal of Statistical Planning and Inference, 2022
- Reconstruction and estimation in the planted partition modelProbability Theory and Related Fields, 2014
- Spectral redemption in clustering sparse networksProceedings of the National Academy of Sciences, 2013
- Improved Bayesian inference for the stochastic block model with application to large networksComputational Statistics & Data Analysis, 2013
- A nonparametric view of network models and Newman–Girvan and other modularitiesProceedings of the National Academy of Sciences, 2009
- Asymptotic equivalence and contiguity of some random graphsRandom Structures & Algorithms, 2009
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- Community structure in social and biological networksProceedings of the National Academy of Sciences, 2002
- The solution of some random NP-hard problems in polynomial expected timeJournal of Algorithms, 1989
- Stochastic blockmodels: First stepsSocial Networks, 1983