子模转换的 Cheeger 不等式
本文引入了一种新的超图拉普拉斯算子,并研究了其光谱。通过该算子的第二小本征值,证明了超图的扩展性和混合时间,并进一步将这些结果推广到了图的节点扩展。
Aug, 2014
该论文研究了高阶重复本征值与稀疏割的关系,探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中,并应用几何考虑进行嵌入的聚类算法的理论基础,并证明了在所有图形中,存在一组大小不超过 2n/k 的集合,其扩展至多为 O (sqrt (λklogk)),从理论上提供了这些算法的近乎最优权衡。
Nov, 2011
介绍了一个广义图拉普拉斯算子,旨在研究超图的特定组合属性,如多路扩展和直径,并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。
May, 2016
本研究介绍了一类具有不同子模割权重的子模割超图,定义了 p-Laplacians 的概念并推导了相应的节点域定理和 k-way Cheeger 不等式,最后描述了计算 1 - 和 2-Laplacians 的算法,构成了新的谱超图聚类方法的基础。
Mar, 2018
基于 1-Laplacian 的非线性谱图理论中,我们研究了特征值的解决方案结构、特征值的极小极大特征和重复定理等多个方面,并计算了几个基本图的特征值及特征向量,同时研究了特征值的图形特征。特别地,对于连通图,Cheeger 恒量等于第一个非零 1-Laplacian 特征值。
Dec, 2014
本研究提出了一组多路双 Cheeger 常数,并证明了在加权有限图上规范化拉普拉斯算子的特征值的普适高阶双 Cheeger 不等式。我们的证明提出了一种基于实射影空间上的度量的新的谱聚类现象。我们进一步将这些结果扩展到一个普遍的可逆马尔可夫算子,并找到了表征其本质频谱的应用。
Jan, 2014
本篇论文通过提出 Cheeger 不等式,利用操作符与图连接拉普拉斯的特征值关系来解决 O (d) 同步问题,并为其频谱方法提供最坏情况下的性能保证。
Apr, 2012