Community detection thresholds and the weak Ramanujan property

Decelle et al. 1 conjectured the existence of a sharp threshold on model parameters for community detection in sparse random graphs drawn from the stochastic block model. Mossel, Neeman and Sly 2 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 self-avoiding paths of a given length ℓ between pairs of nodes. We then prove that for logarithmic length ℓ, 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 weak Ramanujan property of the constructed matrix B. Namely, the spectrum of B consists in two leading eigenvalues ρ(B), λ2 and n -- 2 eigenvalues of a lower order O(nε √ρ(B) for all ε 0, ρ(B) denoting B's spectral radius.