Scarlett, JonathanCevher, Volkan2016-01-192016-01-192016-01-19201610.1109/ISIT.2016.7541630https://infoscience.epfl.ch/handle/20.500.14299/122386WOS:000390098701194In 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.Community detectionstochastic block modelinformation-theoretic limitstext::conference output::conference proceedings::conference paper