Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs
Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs
复制标题
随机图的非回溯谱：群落检测和非正则拉马努金图
DOI：
10.1214/16-aop1142
复制
发表时间：
2018
影响因子：
2.3
通讯作者：
L. Massoulié
中科院分区：
文献类型：
--
作者：
C. Bordenave;M. Lelarge;L. Massoulié
图上的非回溯行走是一条有向路，使得没有边是其前一条边的逆边。图的非回溯矩阵由它的有向边索引，并且可以用来计数给定长度的非回溯行走。它最近被用于社区检测的背景下，并且之前曾出现在与Ihara zeta函数和Ramanujan图的一些概括中。在这项工作中，我们研究的最大特征值的非回溯矩阵的Erdens-Renyi随机图和随机块模型在政权的边的数量是成比例的顶点数。我们的研究结果证实了对称情况下的“光谱救赎猜想”，并表明社区检测可以在可行性阈值以上的领先特征向量的基础上进行。
A nonbacktracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The nonbacktracking matrix of a graph is indexed by its directed edges and can be used to count nonbacktracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the nonbacktracking matrix of the Erdős–Renyi random graph and of the stochastic block model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the “spectral redemption conjecture” in the symmetric case and show that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold.