A Proof of the Block Model Threshold Conjecture

Elchanan Mossel, Joe Neeman, Allan Sly

Research output: Contribution to journalArticle

23 Scopus citations

Abstract

We study a random graph model called the “stochastic 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 classes of vertices, with a within-class edge probability of q and a between-class edge probability of q′. A striking conjecture of Decelle, Krzkala, Moore and Zdeborová [9], 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 q=a/n and q′=b/n, s=(a−b)/2 and d=(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>d and impossible if s2<d. By comparison, until recently the best-known rigorous result showed that clustering is possible if s2>Cdlnd for sufficiently large C. In a previous work, we proved that indeed it is information theoretically impossible to cluster if s2 ≤ d and moreover that it is information theoretically impossible to even estimate the model parameters from the graph when s2 < d. Here we prove the rest of the conjecture by providing an efficient algorithm for clustering in a way that is correlated with the true partition when s2>d. A different independent proof of the same result was recently obtained by Massoulié [20].

Original languageEnglish (US)
Pages (from-to)665-708
Number of pages44
JournalCombinatorica
Volume38
Issue number3
DOIs
StatePublished - Jun 1 2018

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'A Proof of the Block Model Threshold Conjecture'. Together they form a unique fingerprint.

  • Cite this