Finding Sparse Cuts Locally Using Evolving Sets

Details Finding Sparse Cuts Locally Using Evolving Sets Finding Sparse Cuts Locally Using Evolving Sets

2008-11-23

arxiv.org/abs/0811.3779v1

Computer Science

Data Structures and Algorithms

20 pages, no figures

Scientific paper

A {\em 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 {\em 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))$. In comparison, the best previous local partitioning algorithm, due to Andersen, Chung, and Lang, has the same approximation guarantee, but a larger ratio of $O(\phi^{-1} polylog(n))$ between the complexity and output volume. Using our local partitioning algorithm as a subroutine, we construct a fast algorithm for finding balanced cuts. Given a fixed value of $\phi$, the resulting algorithm has complexity $O((m+n\phi^{-1/2}) polylog(n))$ and returns a cut with conductance $O(\phi^{1/2} \log^{1/2} n)$ and volume at least $v_{\phi}/2$, where $v_{\phi}$ is the largest volume of any set with conductance at most $\phi$.

Affiliated with

Also associated with

No associations

Rating

Finding Sparse Cuts Locally Using Evolving Sets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Finding Sparse Cuts Locally Using Evolving Sets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Finding Sparse Cuts Locally Using Evolving Sets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-643817