论文标题
加权不均匀随机图的非折线轨道光谱
Non-backtracking spectra of weighted inhomogeneous random graphs
论文作者
论文摘要
我们研究一个随机图的模型，其中每个边缘是独立绘制（但不一定是相同分布）的模型，然后分配了随机重量。当这种图的平均程度较低时，众所周知，邻接矩阵$ a $的光谱显着偏离了其预期值$ \ mathbb e a $。相比之下，我们表明，在广泛的参数中，非折线矩阵$ b $的顶部特征值 - 一个矩阵，其功率在两个边缘之间进行了非折叠步行的步行，接近$ \ mathbb e a $ a $的矩阵，所有其他特征值和所有其他特征值都限制在已知的garuius中。我们还获得了$ b $的特征向量之间的标量产品的精确表征，并从模型参数得出的确定性对应物。该结果在从（嘈杂的）矩阵完成到社区检测以及矩阵扰动理论等领域中有许多应用。特别是，我们确定了一种推论，即以前仅用于旋转不变的随机矩阵而被建立的被称为Baik-ben唤醒的相变的结果，在轻度浓度假设下，矩阵$ a $均更高。
We study a model of random graphs where each edge is drawn independently (but not necessarily identically distributed) from the others, and then assigned a random weight. When the mean degree of such a graph is low, it is known that the spectrum of the adjacency matrix $A$ deviates significantly from that of its expected value $\mathbb E A$. In contrast, we show that over a wide range of parameters the top eigenvalues of the non-backtracking matrix $B$ -- a matrix whose powers count the non-backtracking walks between two edges -- are close to those of $\mathbb E A$, and all other eigenvalues are confined in a bulk with known radius. We also obtain a precise characterization of the scalar product between the eigenvectors of $B$ and their deterministic counterparts derived from the model parameters. This result has many applications, in domains ranging from (noisy) matrix completion to community detection, as well as matrix perturbation theory. In particular, we establish as a corollary that a result known as the Baik-Ben Arous-Péché phase transition, previously established only for rotationally invariant random matrices, holds more generally for matrices $A$ as above under a mild concentration hypothesis.
