MMJun, 2015

随机图的浓缩和正则化

PDF
TL;DR本文通过研究谱范数中邻接矩阵和拉普拉斯矩阵的浓度来探索随机图与其期望值之间的典型接近程度，其中包括不同概率的独立形成的具有 n 个顶点的不均匀 Erdos-Renyi 随机图，对于稀疏随机图，其期望度数小于 o（logn），需要使这种度数正则化，本文通过一些方法，例如重量重排或删除足够的边等操作来实现，演示了在社区检测问题中，集中结果的应用。
发现论文，激发创造
  • 稀疏随机图：正则化和拉普拉斯的集中

    本文研究了具有可能不同边缘概率的随机图，位于期望度数有限的稀疏区域。通过在邻接矩阵的每个条目中添加数量级为 1/n 的常数，达到正则化的效果，证明了其集中作用，从而证实了在随机块模型下基于正则化谱聚类的一种最简单和最快速的社区检测方法的有效性。

    Feb, 2015

  • 独立边随机图中的邻接矩阵和拉普拉斯矩阵的集中度

    在随机图中，将边权值视为概率，如果最小期望度数为 ω(ln n)，则随机图的邻接矩阵和拉普拉斯矩阵集中于边权为概率的加权图，应用于债券渗透和不均匀随机图问题中，通过引入矩阵 concenetration 和集中不等式得到新的结论。

    Nov, 2009

  • 随机图的集中性与社区检测应用

    本文回顾了随机图在其期望周围的浓缩区域中的不同模式，并讨论了这些浓缩结果在网络社区检测问题中的应用，同时介绍了一些与其相关的随机矩阵理论模型和工具。

    Jan, 2018

  • 边独立随机图的谱

    本文研究随机图模型及其邻接矩阵、拉普拉斯矩阵的谱性质，其中包括对 Erdős-Rényi 图的分析，证明了矩阵与其期望的偏差在一定条件下的上界，并对已有的结果进行了改进。

    Apr, 2012

  • 超图上的高阶随机游走与广义拉普拉斯算子

    本文通过研究高阶超图随机游走，介绍了一组超图拉普拉斯算子以统一超图的不同版本，证明这些拉普拉斯算子的特征值可以有效地控制高阶随机游走的混合速率，推广距离 / 直径和边界扩展。

    Feb, 2011

  • 图谱的近似谱

    本文研究了网络或图谱的光谱问题。在图太大无法明确计算光谱的情况下，提出了一种次线性时间算法，可以计算光谱的简洁表示，并证明了其实用性。同时探讨了该算法在有界度图模型下的属性测试的实际应用。

    Dec, 2017

  • 稀疏非齐次 Erdős-Rényi 图的最大特征值

    研究不均匀的 Erdos-Renyi 图，探究极限特征值的行为，发现其表现出新颖特征，证明最大度数是其一阶特征，并建立了围绕最大度数的特征点交叉。

    Apr, 2017

  • 随机图中归一化拉普拉斯算子的特征向量的极限定理

    本研究证明：在一个有限维的随机点积图的归一化拉普拉斯矩阵的 $d$ 个最大特征值所对应的特征向量的组成部分符合中心极限定理。作为推论，我们证明了对于随机块模型图，归一化拉普拉斯矩阵的谱嵌入的行收敛于多元正态分布，并且每个行的均值和协方差矩阵是其所对应顶点块成员的函数。与邻接矩阵的特征向量的先前结果一起，我们通过多元正态分布之间的 Chernoff 信息比较了嵌入方法选择对后续推理的影响，演示了嵌入方法都不占优势，因此推断潜在块分配的任务无法通过这些嵌入方法获得显著提升。

    Jul, 2016

  • 使用小图谱近似表示大图谱

    本文探讨了粗化对一般图的光谱特性的影响，发现主本征值和本征空间在新旧图拉普拉斯矩阵之间成立。研究结果可以应用于利用粗化的学习算法，尤其是在谱聚类中，该现象缺乏正式的验证。

    Feb, 2018

  • 稀疏随机网络中的社区检测

    考虑在稀疏随机网络中检测紧密社区的问题，将其形式化为在随机图中测试是否存在密集子图。在本文中，我们研究渐近稀疏情况下的信息理论下限，并比较了各种测试方法的性能，发现我们的检测边界是尖锐的。

    Aug, 2013