A proof of the block model threshold conjecture (Q1715062)

The paper under review considers the so-called stochastic block model of random graphs, where each vertex $v\in \{1,2,\ldots n\}$ is assigned (independently and uniformly at random) a label $\sigma_{v}\in \{-1,1\}$ and then $u$ and $v$ are adjacent with probability $q$ if they have the same label and probability $q'$ if they have different labels, again all edges being, conditional on the labelling, independent of each other. For $q=q'$ we recover the Erdős-Rényi random graph model. We focus on the sparse case $q=a/n$, $q'=b/n$ and introduce two parameters $d=(a+b)/2$ and $s=(a-b)/2$. Based on deep but non-rigorous ideas from statistical physics, it was conjectured in [\textit{A. Decelle} et al., ``Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications'', Phys. Rev. E (3) 84, Article ID 066106, 19 p. (2011; \url{doi:10.1103/PhysRevE.84.066106})] that provided $s^2>d$ one can solve the problem, in the sense that one can a.a.s. find a bisection of the graph -- i.e., partition its vertex set -- in a way whose correlation with the ``planted bisection'', i.e., the partition given by the labelling is bounded away from zero. In [Probab. Theory Relat. Fields 162, No. 3--4, 431--461 (2015; Zbl 1320.05113)], the authors of the paper under review had shown that if $s^{2}\leq d$ then the problem cannot be solved in the above sense. Their substantial contribution in this paper is, building on earlier partial results of Coja-Oghlan, to indeed prove the conjecture. Indeed their method is computationally effective and can be implemented in time $O(n\log^{2}(n))$. The result has also been shown independently by \textit{L. Massoulié} [in: Proceedings of the 46th annual ACM symposium on theory of computing, STOC 2014. New York, NY: Association for Computing Machinery (ACM). 694--703 (2014; Zbl 1315.68210)] whose algorithm is spectral but slower than that in the paper under review.