Paper Info
Title
Approximating the Expansion Profile and Almost Optimal Local Graph Clustering
Abstract
Spectral partitioning is a simple, nearly-linear time, algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee of the quality of the approximation found by the algorithm. Local graph partitioning algorithms [ST08, ACL06, AP09] run in time that is nearly linear in the size of the output set, and their approximation guarantee is worse than the guarantee provided by the Cheeger inequalities by a poly-logarithmic $\log^{\Omega(1)} n$ factor. It has been an open problem to design a local graph clustering algorithm with an approximation guarantee close to the guarantee of the Cheeger inequalities and with a running time nearly linear in the size of the output. In this paper we solve this problem, we design an algorithm with the same guarantee (up to a constant factor) as the Cheeger inequality, that runs in time slightly super linear in the size of the output. This is the first sub linear (in the size of the input) time algorithm with almost the same guarantee as the Cheeger's inequality. As a byproduct of our results, we prove a bicriteria approximation algorithm for the expansion profile of any graph. Let $\mu(S)=\sum_{v\in S} d(v)$ be the volume, and $\phi(S):=|E(S, \over line{S})|/\mu(S)$, be the conductance of a set $S$ of vertices. If there is a set of volume at most $\gamma$ and conductance $\phi$, we can find a set of volume at most $\gamma^{1+\eps}$ and conductance at most $O( \sqrt{\phi/\eps} )$, for any $\eps0$. Our proof techniques also provide a simpler proof of the structural result of Arora, Barak, Steurer [ABS10], that can be applied to irregular graphs. Our main technical tool is a lemma stating that, for any set $S$ of vertices of a graph, a lazy $t$-step random walk started from a randomly chosen vertex of $S$, will remain entirely inside $S$ with probability at least $(1-\phi(S)/2)^t$. The lemma also implies a new lower bound to the uniform mixing time of any finite states reversible markov chain.
Year
DOI
Venue
2012
10.1109/FOCS.2012.85
foundations of computer science
Keywords
DocType
Volume
constant factor,bicriteria approximation algorithm,worst-case guarantee,approximation guarantee close,nearly-linear time,expansion profile,almost optimal local graph,local graph,time algorithm,approximation guarantee,output set,cheeger inequality,markov processes,graph theory,approximation theory,computational complexity
Conference
abs/1204.2021
ISSN
ISBN
Citations 
0272-5428
978-1-4673-4383-1
21
PageRank 
References 
Authors
0.73
15
2
Name
Order
Citations
PageRank
Shayan Oveis Gharan132326.63
Luca Trevisan22995232.34