Partitioning into Expanders
Partitioning into Expanders
复制标题
分区为扩展器
DOI：
10.1137/1.9781611973402.93
复制
发表时间：
2013
影响因子：
3.5
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
S. Gharan;L. Trevisan
设G =（V，E）是一个无向图，λk是G的正规拉普拉斯矩阵的第k个最小特征值.代数图论中有一个基本事实：λk > 0当且仅当G至多有k - 1个连通分支。我们证明了这一事实的一个强有力的版本。若λk > 0，则对于某个1 ≤ e ≤ k - 1，V可划分为e个集合P1，.，Pe，使得每个Pi是G中的低电导集合，并诱导出高电导诱导子图。尤其是[方程]和[方程]-扩展器。
我们使我们的结果算法设计一个简单的多项式时间谱算法，找到这样的分区G与二次损失的内部电导的Pi的。与最近关于高阶Cheeger不等式的结果不同，我们的结果没有使用G的高阶本征函数。如果λk和λk+1之间存在足够大的间隙，更准确地说，如果[等式]，那么我们的算法找到V到集合P1，.，Pk，使得导出子图G[Pi]的电导显著大于Pi在G中的电导。这样的划分可以表示G的最佳k个聚类。我们的算法是一个简单的局部搜索，只使用光谱分割算法作为一个子程序。我们期望看到这个简单的算法在聚类应用中的进一步应用。
设ρ（k）= [方程]是G的k阶电导常数，即ρ（k）是V的任意k个不相交子集的最大电导的最小值.我们的主要技术引理表明，如果（1+e）ρ（k）< ρ（k+1），则V可划分为k个集合P1，. Pk使得对于每个1 ≤ i ≤ k，φ（G[Pi]）∈·ρ（k+1）/k且φ（（Pi）≤ k · ρ（k）.这显著地改进了Tanaka [13]的最近结果，Tanaka [13]假设ρ（k）和ρ（k + 1）之间存在指数（以k为单位）间隙。
Let G = (V, E) be an undirected graph, λk be the kth smallest eigenvalue of the normalized laplacian matrix of G. There is a basic fact in algebraic graph theory that λk > 0 if and only if G has at most k -- 1 connected components. We prove a robust version of this fact. If λk > 0, then for some 1 ≤ e ≤ k -- 1, V can be partitioned into e sets P1, ..., Pe such that each Pi is a low-conductance set in G and induces a high conductance induced subgraph. In particular, [EQUATION] and [EQUATION]-expander.
We make our results algorithmic by designing a simple polynomial time spectral algorithm to find such partitioning of G with a quadratic loss in the inside conductance of Pi's. Unlike the recent results on higher order Cheeger's inequality [6, 9], our results does not use higher order eigenfunctions of G. If there is a sufficiently large gap between λk and λk+1, more precisely if [EQUATION] then our algorithm finds a k partitioning of V into sets P1, ..., Pk such that the induced subgraph G[Pi] has a singnificantly larger conductance than the conductance of Pi in G. Such a partitioning may represent the best k clusterings of G. Our algorithm is a simple local search that only uses the Spectral Partitioning algorithm as a subroutine. We expect to see further applications of this simple algorithm in clustering applications.
Let ρ(k) = [EQUATION] be the order k conductance constant of G, in words, ρ(k) is the smallest value of the maximum conductance of any k disjoint subsets of V. Our main technical lemma shows that if (1+e)ρ(k) < ρ(k+1), then V can be partitioned into k sets P1, ..., Pk such that for each 1 ≤ i ≤ k, φ(G[Pi]) ≳ e·ρ(k+1)/k and φ((Pi) ≤ k · ρ(k). This significantly improves a recent result of Tanaka [13] who assumed an exponential (in k) gap between ρ(k) and ρ(k + 1).