Community detection thresholds and the weak Ramanujan property

International audienceDecelle et al.~\cite{Decelle11} conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the {\em stochastic block model}. Mossel, Neeman and Sly~\cite{Mossel12} established the negative part of the conjecture, proving impossibility of non-trivial reconstruction below the threshold. In this work we solve the positive part of the conjecture. To that end we introduce a modified adjacency matrix $B$ which counts {\em self-avoiding} paths of a given length $\ell$ between pairs of nodes. We then prove that for logarithmic length $\ell$, the leading eigenvectors of this modified matrix provide a non-trivial reconstruction of the underlying structure, thereby settling the conjecture. A key step in the proof consists in establishing a {\em weak Ramanujan property} of the constructed matrix $B$. Namely, the spectrum of $B$ consists in two leading eigenvalues $\rho(B)$, $\lambda_2$ and $n-2$ eigenvalues of a lower order $O(n^{\epsilon}\sqrt{\rho(B)})$ for all $\epsilon>0$, $\rho(B)$ denoting $B$'s spectral radius