Decelle–Krzakala–Moore–Zdeborová conjecture on stochastic block model detection

Let $G\sim\mathcal{G}(n,q,a/n,b/n)$ be the stochastic block model with $q\geq 2$ communities, and set

$$d=\frac{a+(q-1)b}{q},\qquad \lambda=\frac{a-b}{a+(q-1)b}.$$

Decelle–Krzakala–Moore–Zdeborová conjecture. For the block model: (I) for all $q$, it is possible to detect communities better than random if $d\lambda^2>1$; (II) for $q\leq 4$, it is information theoretically impossible to predict better than random if $\lambda\geq 0$ and $d\lambda^2<1$; and (III) for $q\geq 5$, it is information theoretically possible to predict better than random for some $\lambda$ with $d\lambda^2<1$, but not in a computationally efficient way.

These predictions identify the Kesten–Stigum threshold and the conjectured computational-statistical gap in sparse community detection. The paper states that part I was established in subsequent work, while parts II and III had only partial rigorous support at this point.