Partial Recovery Bounds for the Sparse Stochastic Block Model
This work addresses the fundamental limits of community recovery in sparse networks, which is incremental as it builds on existing stochastic block model literature.
The paper tackles the problem of community detection in the sparse stochastic block model by deriving information-theoretic upper and lower bounds on the average proportion of community labels recovered, with near-matching bounds for moderate parameter differences and exact matching in the limit as the difference grows large.
In this paper, we study the information-theoretic limits of community detection in the symmetric two-community stochastic block model, with intra-community and inter-community edge probabilities $\frac{a}{n}$ and $\frac{b}{n}$ respectively. We consider the sparse setting, in which $a$ and $b$ do not scale with $n$, and provide upper and lower bounds on the proportion of community labels recovered on average. We provide a numerical example for which the bounds are near-matching for moderate values of $a - b$, and matching in the limit as $a-b$ grows large.