Community Detection in the Stochastic Block Model: fundamental limits

Abstract

In recent years, there have been many developments in the study of the stochastic block model, starting with a paper by Decelle et al. in which they conjecture that in the sparse stochastic block model, efficient community detection is possible if and only if the parameters are above the Kesten-Stigum bound. Massouli\'e , Mossel et al., and Bordenave et al. succeeded in proving the positive half of this conjecture in the $2$-community symmetric case. Also, Mossel et al. proved that community detection is impossible below the KS bound in the $2$-community symmetric case. On another note, Abbe et al. and Mossel et al. found a threshold for when it was possible to completely recover the communities in the $2$-community symmetric case.

In this thesis, we go beyond the $2$-community symmetric case to prove the positive half of the conjecture for the general SBM. In order to do that, we construct a linearized belief propagation algorithm that runs in $O(n\log n)$ time and prove that it detects communities whenever the parameters of the SBM are above the KS bound. We also prove that unlike in the $2$-community symmetric case, in the general SBM there are choices of parameters below the KS threshold for which one can detect communities in exponential time, confirming another conjecture by Decelle et al. This result implies that we cannot prove the impossibility of efficient community detection below the KS bound without proving some major conjectures on what compuations can be done efficiently. We also extend the threshold for when it is possible to completely recover the communities to the general SBM.