Community detection thresholds and the weak Ramanujan property
Community detection thresholds and the weak Ramanujan property
复制标题
DOI：
10.1145/2591796.2591857
复制
发表时间：
2013-11
期刊：
影响因子：
--
通讯作者：
L. Massoulié
中科院分区：
文献类型：
--
作者：
L. Massoulié
德塞尔等人。 [1]推测在随机块模型绘制的稀疏随机图中社区检测的模型参数存在尖锐阈值。 Mossel、Neeman 和 Sly [2] 建立了猜想的否定部分，证明了低于阈值的非平凡重建是不可能的。在这项工作中，我们解决了猜想的积极部分。为此，我们引入了一个修改后的邻接矩阵 B，它计算节点对之间给定长度 ℓ 的自回避路径。然后我们证明，对于对数长度 ℓ，该修改矩阵的前导特征向量提供了基础结构的非平凡重建，从而解决了猜想。证明的关键步骤在于建立所构造矩阵 B 的弱拉马努金性质。即，B 的谱由两个前导特征值 ρ(B)、λ2 和 n -- 2 个低阶 O(nε √ρ(B) 特征值组成，对于所有 ε 0，ρ(B) 表示 B 的谱半径。
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.