The Kesten–Stigum conjecture for symmetric stochastic block models

Let $(X,G)$ be drawn from the symmetric stochastic block model $\mathrm{SSBM}(n,k,a/n,b/n)$ with $k$ communities, probability $a/n$ inside the communities and $b/n$ across. Define

$$\mathrm{SNR}=\frac{(a-b)^2}{k(a+(k-1)b)}.$$

Kesten–Stigum conjecture. For any $k\geq 2$, if $\mathrm{SNR}>1$, it is possible to detect communities in polynomial time. If $k\geq 4$, it is possible to detect communities information-theoretically for some $\mathrm{SNR}$ strictly below $1$.

This conjecture predicts both the algorithmic threshold at the Kesten–Stigum threshold and an information-theoretic transition below it for sufficiently many communities. The source notes that $k=5$ is necessary under the constraint $a>b$, whereas $k=4$ suffices in general, and that the second transition is more precise for $k\geq4$ while $k=3$ has a single threshold.