Nov, 2011

多路谱分割和高阶 Cheeger 不等式

PDF
TL;DR该论文研究了高阶重复本征值与稀疏割的关系，探讨了利用底部 k 个本征向量将顶点嵌入到 R^k 中，并应用几何考虑进行嵌入的聚类算法的理论基础，并证明了在所有图形中，存在一组大小不超过 2n/k 的集合，其扩展至多为 O (sqrt (λklogk))，从理论上提供了这些算法的近乎最优权衡。
发现论文，激发创造
  • 改进的 Cheeger 不等式：通过高阶谱间隙分析谱分裂算法

    该研究证明了基于谱的划分算法可以在保证性能的同时，实现稀疏切割，同时将分析扩展到其他图划分问题中。

    Jan, 2013

  • 通过更高的特征值实现许多的稀疏割

    该论文研究了通过 Laplacian 矩阵中的特征值来优化图的分割，提出了基于谱投影和随机取整的多项式时间算法，并证明得到的上限是最优的。

    Nov, 2011

  • 超图马尔可夫算子、特征值和近似算法

    本文引入了一种新的超图拉普拉斯算子，并研究了其光谱。通过该算子的第二小本征值，证明了超图的扩展性和混合时间，并进一步将这些结果推广到了图的节点扩展。

    Aug, 2014

  • 扩张图的划分

    本文介绍了一种使用谱算法的简单多项式时间用于进行图分割的方法，旨在寻找具有网络传导性和诱导子图的低导纳集合，并且提出了一种找到最佳 k 聚类的方法，其中 k 是一个整数，而且这种方法与 Cheeger's inequality 有所不同。

    Sep, 2013

  • 超图拉普拉斯的光谱性质和近似算法

    介绍了一个广义图拉普拉斯算子，旨在研究超图的特定组合属性，如多路扩展和直径，并使用扩散过程和程序化最小化器来优化 Cheeger 不等式和 k-th 程序化最小化器。

    May, 2016

  • 图的多路径双赫格常数与谱界

    本研究提出了一组多路双 Cheeger 常数，并证明了在加权有限图上规范化拉普拉斯算子的特征值的普适高阶双 Cheeger 不等式。我们的证明提出了一种基于实射影空间上的度量的新的谱聚类现象。我们进一步将这些结果扩展到一个普遍的可逆马尔可夫算子，并找到了表征其本质频谱的应用。

    Jan, 2014

  • 子模转换的 Cheeger 不等式

    通过引入子模变换的概念并定义其 Laplacian 和规范化 Laplacian，本文综合和概括了现有的 Cheeger 不等式，并且引出新的 Cheeger 不等式。本文还提出了一种多项式时间的保证算法，以计算子模变换的规范化 Laplacian 的最小非平凡特征值。

    Aug, 2017

  • 图上 1 - 拉普拉斯算子和 Cheeger 常数的谱

    基于 1-Laplacian 的非线性谱图理论中，我们研究了特征值的解决方案结构、特征值的极小极大特征和重复定理等多个方面，并计算了几个基本图的特征值及特征向量，同时研究了特征值的图形特征。特别地，对于连通图，Cheeger 恒量等于第一个非零 1-Laplacian 特征值。

    Dec, 2014

  • 近似扩张剖面和几乎最优局部图聚类

    本文提出了能够在接近于线性的时间内找到稀疏切割的近似算法，解决了设计拥有近似保证的局部图聚类算法的开放性问题，并且其近似保证与 Cheeger 不等式相当。

    Apr, 2012

  • 带符号图的 Cheeger 常数、结构平衡和谱聚类分析

    该论文介绍了一种家族型的多路 Cheeger 常数，在有符号的图形中引入了一种度量双重性，以及用于找到近似平衡子图的谱聚类方法，并使用签署的拉普拉斯矩阵估计了极端特征值。

    Nov, 2014