A Proof Of The Block Model Threshold Conjecture

We study a random graph model named the "block model" in statistics and the "planted partition model" in theoretical computer science. In its simplest form, this is a random graph with two equal-sized clusters, with a between-class edge probability of q and a within-class edge probability of p. A striking conjecture of Decelle, Krzkala, Moore and Zdeborov'a based on deep, non-rigorous ideas from statistical physics, gave a precise prediction for the algorithmic threshold of clustering in the sparse planted partition model. In particular, if p = a/n and q = b/n, s=(a-b)/2 and p=(a+b)/2 then Decelle et al. conjectured that it is possible to efficiently cluster in a way correlated with the true partition if s2 > p and impossible if s2 < p. By comparison, the best-known rigorous result is that of Coja-Oghlan, who showed that clustering is possible if s2 > C p ln p for some sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to to cluster if s2 < p and furthermore it is information theoretically impossible to even estimate the model parameters from the graph when s2 < p. Here we complete the proof of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s2 > p. A different independent proof of the same result was recently obtained by Laurent Massoulie.