This is the authors' abstract. We don't add key points for this paper.
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.
Answers are grounded in this paper and cite their sources.
No takes yet. Share an insight, caveat, or question.
Laurent Massoulié (2014) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: