Community detection thresholds and the weak Ramanujan property

Abstract

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

References in corpus (2)

• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Community Detection in the Labelled Stochastic Block Model

Cited by in corpus (5)

• Accurate Community Detection in the Stochastic Block Model via Spectral Algorithms
• Stochastic Block Model and Community Detection in the Sparse Graphs: A spectral algorithm with optimal rate of recovery
• Network Cross-Validation for Determining the Number of Communities in Network Data
• Side Information in the Binary Stochastic Block Model: Exact Recovery
• Asymptotic Optimality of Constant-Order Policies for Lost Sales Inventory Models with Large Lead Times