对于一大类随机拉普拉斯矩阵来说,最大特征值与最大对角线元素的大小关系是紧的。其中最大特征值可以用半正定松弛方法解决,从而解决了一些凸松弛算法紧度的问题。这也可以解释 Erdős-Rényi 图的连通阈值和谱范数矩阵估计等问题。
Apr, 2015
本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质,其中包括对 Erdős-Rényi 图的分析,证明了矩阵与其期望的偏差在一定条件下的上界,并对已有的结果进行了改进。
Apr, 2012
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
本文研究了 Erdős-Rényi 随机图的邻接矩阵集合,证明了该集合的密度满足长于 $N^{-1}$ 的谱窗口的 Wigner 半圆律,证明了所有特征向量均被证明是完全分散的。
Mar, 2011
本文基于高斯正交、幺正及交叉矩阵集合,在精确计算了最大(最小)特征值偏离的概率后,证明了特征值均为正数(负数)的概率随着 N 的增大而下降,同时计算了特征值落在给定区间内的概率,以此推导出最大值和最小值特征值的联合概率分布并得出了特征向量密度的平均密度。
Jan, 2008
本文采用 Talagrand 的不等式证明了各种随机对称矩阵的前几个最大的(也是最重要的)特征值非常强烈地集中。这种强烈的集中现象使我们能够高精度地计算这些特征值的均值。我们的方法非常不同于传统方法。
Sep, 2000
研究了均匀多重超图的邻接张量的 $H$ 和 $E/Z$ 特征值,并给出了最大正 $H$ 或 $Z$ 特征值对应严格正特征向量的条件。此外,还研究了邻接张量的 $E$ 谱是否对称。
Sep, 2012
证明了对于正则随机图 Gn,d (d→∞),该图的特征值的半圆律,补充了 McKay 在固定 d 的情况下的先前研究结果。同时,对 Erdős-Rényi 随机图 G (n,p) 特征向量的无穷范数得出了上限,回答了 Dekel-Lee-Linial 的问题。
Nov, 2010
本研究证明:在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论,我们证明了对于随机块模型图,归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布,并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起,我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响,演示了嵌入方法都不占优势,因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
Jul, 2016
在随机图中,将边权值视为概率,如果最小期望度数为 ω(ln n),则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图,应用于债券渗透和不均匀随机图问题中,通过引入矩阵 concenetration 和集中不等式得到新的结论。
Nov, 2009