Abstract

In a paper that initiated the modern study of the stochastic block model, Decelle et al., backed by Mossel et al., made the following conjecture: Denote by $k$ the number of balanced communities, $a/n$ the probability of connecting inside communities and $b/n$ across, and set $\mathrm{SNR}=(a-b)^{2}/(k(a+(k-1)b)$ ; for any $k\geq 2$ , it is possible to detect communities efficiently whenever $\mathrm{SNR}>1$ (the KS threshold), whereas for $k\geq 4$ , it is possible to detect communities information-theoretically for some $\mathrm{SNR}<1$ . Massoulié, Mossel et al. and Bordenave et al. succeeded in proving that the KS threshold is efficiently achievable for $k=2$ , while Mossel et al. proved that it cannot be crossed information-theoretically for $k=2$ . The above conjecture remained open for $k\geq 3$ .