finding sparse cuts locally using evolving sets
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 ?.
evolving sets graph partitioning local algorithms