Expander Decomposition and Pruning: Faster, Stronger, and Simpler
Expander Decomposition and Pruning: Faster, Stronger, and Simpler
复制标题
DOI：
10.1137/1.9781611975482.162
复制
发表时间：
2018-12
期刊：
影响因子：
--
通讯作者：
Thatchaphol Saranurak;Di Wang
中科院分区：
文献类型：
--
作者：
Thatchaphol Saranurak;Di Wang
我们研究图聚类问题，其目标是将图划分为簇，即顶点的不相交子集，使得每个簇内部连接良好，同时与图的其余部分稀疏连接。特别是，我们使用由 Kannan、Vempala 和 Vetta 激发的自然双标准概念，我们将其称为 {\em 扩展器分解}。扩展器分解已成为快速图算法设计中的构建模块之一，尤其是 Spielman 和 Teng 的近线性时间拉普拉斯求解器，它在实践中也有广泛的应用。我们设计了扩展器分解的参数化版本的算法，其中给定 $m$ 边的图 $G$ 和参数 $\phi$，我们的算法找到将顶点划分为簇，使得每个簇产生至少 $\phi$ 的电导子图（即 $\phi$ 扩展器），并且 $G$ 中只有 $\widetilde{O}(\phi)$ 部分边具有跨不同簇的端点。我们的算法运行时间为 $\widetilde{O}(m/\phi)$，并且是第一个当 $\phi$ 至少为 $1/\log^{O(1)} m$ 时的近线性时间算法，这是大多数实际设置和理论应用中的情况。以前的结果要么花费 $\Omega(m^{1+o(1)})$ 时间，要么达到接近线性的时间，但扩展保证较弱，其中保证每个输出簇包含在某个未知的 $\phi$ 扩展器中。我们的结果既实现了近线性的运行时间，又为集群提供了强有力的扩展保证。此外，我们为结果开发的主要技术可以应用于获得更好的 emph{expander 剪枝}算法，这是在动态图上维护扩展器分解的关键工具。最后，我们注意到我们的算法是根据相对简单和基本的技术的第一原理开发的，因此使其很可能实用。
We study the problem of graph clustering where the goal is to partition a graph into clusters, i.e. disjoint subsets of vertices, such that each cluster is well connected internally while sparsely connected to the rest of the graph. In particular, we use a natural bicriteria notion motivated by Kannan, Vempala, and Vetta which we refer to as {\em expander decomposition}. Expander decomposition has become one of the building blocks in the design of fast graph algorithms, most notably in the nearly linear time Laplacian solver by Spielman and Teng, and it also has wide applications in practice. We design algorithm for the parametrized version of expander decomposition, where given a graph $G$ of $m$ edges and a parameter $\phi$, our algorithm finds a partition of the vertices into clusters such that each cluster induces a subgraph of conductance at least $\phi$ (i.e. a $\phi$ expander), and only a $\widetilde{O}(\phi)$ fraction of the edges in $G$ have endpoints across different clusters. Our algorithm runs in $\widetilde{O}(m/\phi)$ time, and is the first nearly linear time algorithm when $\phi$ is at least $1/\log^{O(1)} m$, which is the case in most practical settings and theoretical applications. Previous results either take $\Omega(m^{1+o(1)})$ time, or attain nearly linear time but with a weaker expansion guarantee where each output cluster is guaranteed to be contained inside some unknown $\phi$ expander. Our result achieve both nearly linear running time and the strong expander guarantee for clusters. Moreover, a main technique we develop for our result can be applied to obtain a much better \emph{expander pruning} algorithm, which is the key tool for maintaining an expander decomposition on dynamic graphs. Finally, we note that our algorithm is developed from first principles based on relatively simple and basic techniques, thus making it very likely to be practical.