A Cheeger Inequality for Size-Specific Conductance
A Cheeger Inequality for Size-Specific Conductance
复制标题
特定尺寸电导的 Cheeger 不等式
DOI：
10.48550/arxiv.2303.11452
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
D. Gleich
中科院分区：
文献类型：
--
作者：
Yufan Huang;D. Gleich
由Lovasz和Simonovits提出的$\mu$-电导测量是一个大小特定的电导分数，它识别具有最小电导的集合，而忽略那些体积小于整个图的$\mu$分数的集合。使用$\mu$-电导使我们能够以新的方式进行研究。在这篇手稿中，我们提出了一个修改的谱截，它是$\mu$-电导的整数规划的自然松弛，并表明该规划的最优解具有$\mu$-电导的双边Cheeger不等式。
The $\mu$-conductance measure proposed by Lovasz and Simonovits is a size-specific conductance score that identifies the set with smallest conductance while disregarding those sets with volume smaller than a $\mu$ fraction of the whole graph. Using $\mu$-conductance enables us to study in new ways. In this manuscript we propose a modified spectral cut that is a natural relaxation of the integer program of $\mu$-conductance and show the optimum of this program has a two-sided Cheeger inequality with $\mu$-conductance.
低秩半定规划的网络社区概况的理论界限
DOI：
--
发表时间：
2023
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
Yufan Huang, C. Seshadhri
通讯作者：
Yufan Huang, C. Seshadhri