稀疏随机图:特征值和特征向量
本文研究了 Erdős-Rényi 随机图的邻接矩阵集合,证明了该集合的密度满足长于 $N^{-1}$ 的谱窗口的 Wigner 半圆律,证明了所有特征向量均被证明是完全分散的。
Mar, 2011
研究了顶点数为 $N$,每个顶点度数为 $d$ 的 $d$-regular 随机图的谱特性,得出了这些图的距离谱特性与 Wigner 半圆律高度吻合,从而证明了所有特征向量的完全离散与量子唯一性吗的概率版本。
Mar, 2015
本文研究随机 d - 正则图的第二特征值的概率问题,证明了 Noga Alon 的猜想,并计算了该概率在大多数情况下都以 1/n 的多项式速度衰减。
May, 2004
本研究证明:在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论,我们证明了对于随机块模型图,归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布,并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起,我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响,演示了嵌入方法都不占优势,因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
Jul, 2016
该论文证明了随机矩阵的经验谱分布在维数趋近无穷大时趋近于单位圆上的均匀分布,特别是对于高斯模型,作者给出了 Silverstein 公式证明;而对于重尾模型,作者使用 Aldous 和 Steele 的方法得到了相应的结论。
Sep, 2011
通过先进的算法,研究人员开发了新方法,以确定与实际网络模型对应的邻接矩阵的特征值,并发现了有趣的结果,指出相关图的频谱代表了分类图的实用工具,并可提供有关实际网络的相关结构特性的有用见解。
Feb, 2001
研究不均匀的 Erdos-Renyi 图,探究极限特征值的行为,发现其表现出新颖特征,证明最大度数是其一阶特征,并建立了围绕最大度数的特征点交叉。
Apr, 2017
对于一大类随机拉普拉斯矩阵来说,最大特征值与最大对角线元素的大小关系是紧的。其中最大特征值可以用半正定松弛方法解决,从而解决了一些凸松弛算法紧度的问题。这也可以解释 Erdős-Rényi 图的连通阈值和谱范数矩阵估计等问题。
Apr, 2015
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
本文介绍了利用图的随机行走矩阵的前 k 个非平凡特征向量对图进行谱嵌入的方法,并使用此框架限制了所有图的所有特征值,并提出了一种新的工具 —— 谱嵌入,在分析可逆马尔可夫链中使用。
Nov, 2012