Community detection thresholds and the weak Ramanujan property

摘要: Decelle et al.\cite{Decelle11} conjectured the existence of a sharp threshold for community detection in sparse random graphs drawn from stochastic block model. Mossel al.\cite{Mossel12} established negative part conjecture, proving impossibility meaningful below threshold. However positive conjecture remained elusive so far. Here we solve conjecture. We introduce modified adjacency matrix $B$ that counts self-avoiding paths given length $\ell$ between pairs nodes and prove logarithmic $\ell$, leading eigenvectors this provide non-trivial detection, thereby settling A key step proof consists establishing {\em weak Ramanujan property} $B$. Namely, spectrum two eigenvalues $\rho(B)$, $\lambda_2$ $n-2$ lower order $O(n^{\epsilon}\sqrt{\rho(B)})$ all $\epsilon>0$, $\rho(B)$ denoting $B$'s spectral radius. $d$-regular are when their second eigenvalue verifies $|\lambda|\le 2 \sqrt{d-1}$. Random have largest $\lambda$ $2\sqrt{d-1}+o(1)$ (see Friedman\cite{friedman08}), thus being almost} Ramanujan. Erd\H{o}s-R\'enyi with average degree $d$ at least ($d=\Omega(\log n)$) $O(\sqrt{d})$ Feige Ofek\cite{Feige05}), slightly weaker version property. separation property fails ($d=O(1)$) graphs. Our result shows by constructing through neighborhood expansion, regularize original to eventually recover form