Computer Science/Discrete Mathematics Seminar I

A local graph partitioning algorithm finds a set of vertices with small conductance (i.e. a sparse cut) by adaptively exploring part of 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 that it outputs, with at most a weak dependence on the number $n$ 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 $\phi$, for at least half of the starting vertices in $A$ our algorithm will output (with probability at least half), a set of conductance $O(\phi^{1/2} \log^{1/2} n)$. We prove that for a given run of the algorithm, the expected ratio between its computational complexity and the volume of the set that it outputs is $O(\phi^{-1/2} polylog(n))$. (Joint work with Reid Andersen, Live Labs Microsoft).