STOC Conference 2009 Conference Paper
Finding sparse cuts locally using evolving sets
- Reid Andersen
- Yuval Peres
A local graph partitioning algorithm finds a set of vertices with small conductance (i.e.~a sparse cut) by adaptively exploring a large graph G, starting from a specified vertex. For the algorithm to be local, its complexity must be bounded in terms of the size of the set it outputs, with at most a weak dependence on n, the number of vertices in G. Previous local partitioning algorithms find sparse cuts using random walks and personalized PageRank. In this paper, we introduce a randomized local partitioning algorithm that finds a sparse cut by simulating the volume-biased evolving set process , which is a Markov chain on sets of vertices. We prove that for any set of vertices A that has conductance at most φ, and for at least half of the starting vertices in A, our algorithm will output (with probability at least half) a set of conductance O(φ 1/2 log 1/2 n). The complexity of a local partitioning algorithm is measured by its work/volume ratio, which is the ratio between the computational complexity of the algorithm on a given run, and the volume of the set output. We prove that for our algorithm, the expected value of the work/volume ratio is polylognoparen(φ -1/2 ). The best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee but a larger work/volume ratio of polylognoparen(φ -1 ). As an application of our local partitioning algorithm, we construct a fast algorithm for finding balanced cuts. The resulting algorithm takes as input a graph and a fixed value of φ, has complexity polylog{m+nφ -1/2 ), and returns a cut with conductance O(φ 1/2 log 1/2 n) and volume at least v φ /2, where v φ is the volume of the largest set in the graph with conductance at most φ.