介绍了一个广义图拉普拉斯算子,旨在研究超图的特定组合属性,如多路扩展和直径,并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
本文引入了一种新的超图拉普拉斯算子,并研究了其光谱。通过该算子的第二小本征值,证明了超图的扩展性和混合时间,并进一步将这些结果推广到了图的节点扩展。
Aug, 2014
该论文通过扩展连续扩散过程及其拉普拉斯算子,在超图上定义出一个家族算子,其谱特性与超图电导率相关,并提供了一个强有力的工具来增强谱超图理论的发展。
Apr, 2018
通过引入子模变换的概念并定义其 Laplacian 和规范化 Laplacian,本文综合和概括了现有的 Cheeger 不等式,并且引出新的 Cheeger 不等式。本文还提出了一种多项式时间的保证算法,以计算子模变换的规范化 Laplacian 的最小非平凡特征值。
Aug, 2017
该论文研究了高阶重复本征值与稀疏割的关系,探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中,并应用几何考虑进行嵌入的聚类算法的理论基础,并证明了在所有图形中,存在一组大小不超过 2n/k 的集合,其扩展至多为 O (sqrt (λklogk)),从理论上提供了这些算法的近乎最优权衡。
Nov, 2011
本研究提出了一组多路双 Cheeger 常数,并证明了在加权有限图上规范化拉普拉斯算子的特征值的普适高阶双 Cheeger 不等式。我们的证明提出了一种基于实射影空间上的度量的新的谱聚类现象。我们进一步将这些结果扩展到一个普遍的可逆马尔可夫算子,并找到了表征其本质频谱的应用。
Jan, 2014
通过引入不同的连通性矩阵(如邻接、拉普拉斯和标准化拉普拉斯矩阵),我们研究了非均匀超图的基础加权图的谱特性,并展示了这些矩阵的谱特性可以很好地研究超图的不同结构特性。通过这些操作符的特征值研究超图的连通性。通过对 Laplacian 矩阵和标准化 Laplacian 矩阵的最小非平凡特征值进行边界限制来定义超图上的 Cheeger 恒量。此外,我们还介绍了关于超图上的 Ricci 曲率的两种不同方法。
Nov, 2017
基于 1-Laplacian 的非线性谱图理论中,我们研究了特征值的解决方案结构、特征值的极小极大特征和重复定理等多个方面,并计算了几个基本图的特征值及特征向量,同时研究了特征值的图形特征。特别地,对于连通图,Cheeger 恒量等于第一个非零 1-Laplacian 特征值。
Dec, 2014
该研究证明了基于谱的划分算法可以在保证性能的同时,实现稀疏切割,同时将分析扩展到其他图划分问题中。
Jan, 2013
本文通过研究高阶超图随机游走,介绍了一组超图拉普拉斯算子以统一超图的不同版本,证明这些拉普拉斯算子的特征值可以有效地控制高阶随机游走的混合速率,推广距离 / 直径和边界扩展。
Feb, 2011