边独立随机图的谱
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
在随机图中,将边权值视为概率,如果最小期望度数为 ω(ln n),则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图,应用于债券渗透和不均匀随机图问题中,通过引入矩阵 concenetration 和集中不等式得到新的结论。
Nov, 2009
本文研究了网络或图谱的光谱问题。在图太大无法明确计算光谱的情况下,提出了一种次线性时间算法,可以计算光谱的简洁表示,并证明了其实用性。同时探讨了该算法在有界度图模型下的属性测试的实际应用。
Dec, 2017
介绍了一个广义图拉普拉斯算子,旨在研究超图的特定组合属性,如多路扩展和直径,并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
研究不均匀的 Erdos-Renyi 图,探究极限特征值的行为,发现其表现出新颖特征,证明最大度数是其一阶特征,并建立了围绕最大度数的特征点交叉。
Apr, 2017
通过引入不同的连通性矩阵(如邻接、拉普拉斯和标准化拉普拉斯矩阵),我们研究了非均匀超图的基础加权图的谱特性,并展示了这些矩阵的谱特性可以很好地研究超图的不同结构特性。通过这些操作符的特征值研究超图的连通性。通过对 Laplacian 矩阵和标准化 Laplacian 矩阵的最小非平凡特征值进行边界限制来定义超图上的 Cheeger 恒量。此外,我们还介绍了关于超图上的 Ricci 曲率的两种不同方法。
Nov, 2017
本文引入了一种新的超图拉普拉斯算子,并研究了其光谱。通过该算子的第二小本征值,证明了超图的扩展性和混合时间,并进一步将这些结果推广到了图的节点扩展。
Aug, 2014
本研究证明:在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论,我们证明了对于随机块模型图,归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布,并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起,我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响,演示了嵌入方法都不占优势,因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
Jul, 2016
本文研究了 Erdős-Rényi 随机图的邻接矩阵集合,证明了该集合的密度满足长于 $N^{-1}$ 的谱窗口的 Wigner 半圆律,证明了所有特征向量均被证明是完全分散的。
Mar, 2011