Partial Recovery Bounds for the Sparse Stochastic Block Model

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.


Published in:
2016 Ieee International Symposium On Information Theory, 1904-1908
Presented at:
International Symposium on Information Theory (ISIT), Barcelona, July 10-15, 2016
Year:
2016
Publisher:
New York, Ieee
ISBN:
978-1-5090-1806-2
Keywords:
Laboratories:




 Record created 2016-01-19, last modified 2018-03-17

Publisher's version:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)