独立边随机图中的邻接矩阵和拉普拉斯矩阵的集中度
本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度,其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图,对于稀疏随机图,其期望度数小于 o(logn),需要使这种度数正则化,本文通过一些方法,例如重量重排或删除足够的边等操作来实现,演示了在社区检测问题中,集中结果的应用。
Jun, 2015
本文研究了具有可能不同边缘概率的随机图,位于期望度数有限的稀疏区域。通过在邻接矩阵的每个条目中添加数量级为 1/n 的常数,达到正则化的效果,证明了其集中作用,从而证实了在随机块模型下基于正则化谱聚类的一种最简单和最快速的社区检测方法的有效性。
Feb, 2015
本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质,其中包括对 Erdős-Rényi 图的分析,证明了矩阵与其期望的偏差在一定条件下的上界,并对已有的结果进行了改进。
Apr, 2012
本研究证明:在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论,我们证明了对于随机块模型图,归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布,并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起,我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响,演示了嵌入方法都不占优势,因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。
Jul, 2016
本文通过研究高阶超图随机游走,介绍了一组超图拉普拉斯算子以统一超图的不同版本,证明这些拉普拉斯算子的特征值可以有效地控制高阶随机游走的混合速率,推广距离 / 直径和边界扩展。
Feb, 2011
通过概率测度采样子流形在欧几里得空间的样本,可以构造一个邻域图,作为子流形的近似。本文确定了文献中使用的三种不同图 Laplacian 在样本大小增加且邻域大小趋近于零时的点态极限。我们表明,在子流形上的均匀测度下,所有图 Laplacians 在常数的意义下均具有相同的极限。然而,对于在子流形上的非均匀测度的情况,只有所谓的随机游走图 Laplacian 收敛于加权 Laplace-Beltrami 算子。
Aug, 2006
我们研究了从组合 Laplacians 获得的混合密度矩阵的纠缠特性。我们介绍了图形的密度矩阵的概念。我们对具有纯密度矩阵的图形进行了表征,并展示了图的密度矩阵总可以表示为图形的纯密度矩阵的均匀混合物。我们考虑了这些矩阵的 von Neumann 熵,并表征了最小值和最大值所对应的图。然后,我们讨论了分离性问题,并指出图的密度矩阵的可分离性并不总是取决于顶点的标号。我们考虑具有张量积结构的图形和与状态的纠缠相关的组合性质的简单情况。我们计算了表示纠缠状态的四个顶点的所有图形的紧密性。结果发现,对于其中一些图形,紧密性的值恰好是分数。
Jun, 2004
介绍了一个广义图拉普拉斯算子,旨在研究超图的特定组合属性,如多路扩展和直径,并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
本文介绍了一种扩展了边远离独立性的稀疏随机图的一般模型,并且通过构造非齐性随机超图来替代每个超边,再通过与某个积分算子的范数相关来解释巨型连通性的临界点,并将该巨型连通量与某些(非 Poisson)多类型分支过程的生存概率关联起来,同时研究度分布和数量小子图的细节。
Jul, 2008