2014 · 338 citations · 16 references
EngineeringComputer ScienceComplex SystemsInformation TheoryStochastic ProcessesCommunity DetectionCommunity StructureGraph AlgorithmsGraph TheoryStochastic NetworksEigenvaluesRandom Graph TheoryRandom GraphsSelf-avoiding WalksSparse Random GraphsSpectral Graph TheorySpectral RadiusThreshold Phenomena
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.
16
Stochastic blockmodels: First steps
Paul W. Holland, Kathryn Blackmond Laskey, Samuel Leinhardt · Social Networks · 1983 · 2.9K citations
Choice Reviews Online · 1992 · 1.5K citations
The eigenvalues of random symmetric matrices
Zoltán Füredi, János Komlós · COMBINATORICA · 1981 · 673 citations
Spectral redemption in clustering sparse networks
Florent Krząkała, Cristopher Moore, Elchanan Mossel et al. · Proceedings of the National Academy of Sciences · 2013 · 657 citations · Full text