Uncertainty quantification and testing in a stochastic block model with two unequal communities
Authors:
Preprint
Abstract
We show posterior convergence for the community structure in the planted bi-section model, for several interesting priors. Examples include where the label on each vertex is iid Bernoulli distributed, with some parameter $r\in(0,1)$. The parameter $r$ may be fixed, or equipped with a beta distribution. We do not have constraints on the class sizes, which might be as small as zero, or include all vertices, and everything in between. This enables us to test between a uniform (Erd\"os-R\'enyi) random graph with no distinguishable community or the planted bi-section model. The exact bounds for posterior convergence enable us to convert credible sets into confidence sets. Symmetric testing with posterior odds is shown to be consistent.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Achieving Exact Cluster Recovery Threshold via Semidefinite ProgrammingIEEE Transactions on Information Theory, 2016
- 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
- Stochastic blockmodels with a growing number of classesBiometrika, 2012
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applicationsPhysical Review E, 2011
- Inference and Phase Transitions in the Detection of Modules in Sparse NetworksPhysical Review Letters, 2011
- A nonparametric view of network models and Newman–Girvan and other modularitiesProceedings of the National Academy of Sciences, 2009
- 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