Local Graph Partitioning using PageRank Vectors
- 1 January 2006
- conference paper
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 475-486
- https://doi.org/10.1109/focs.2006.44
Abstract
A local graph partitioning algorithm finds a cut near a specified starting vertex, with a running time that depends largely on the size of the small side of the cut, rather than the size of the input graph. In this paper, we present a local partitioning algorithm using a variation of PageRank with a specified starting distribution. We derive a mixing result for PageRank vectors similar to that for random walks, and show that the ordering of the vertices produced by a PageRank vector reveals a cut with small conductance. In particular, we show that for any set C with conductance Phi and volume k, a PageRank vector with a certain starting distribution can be used to produce a set with conductance (O(radic(Phi log k)). We present an improved algorithm for computing approximate PageRank vectors, which allows us to find such a set in time proportional to its size. In particular, we can find a cut with conductance at most oslash, whose small side has volume at least 2b in time O(2 log m/(2b log2 m/oslash2) where m is the number of edges in the graph. By combining small sets found by this local partitioning algorithm, we obtain a cut with conductance oslash and approximately optimal balance in time O(m log4 m/oslash)Keywords
This publication has 14 references indexed in Scilit:
- Local Graph Partitioning using PageRank VectorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Exploring the community structure of newsgroupsPublished by Association for Computing Machinery (ACM) ,2004
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systemsPublished by Association for Computing Machinery (ACM) ,2004
- Topic-sensitive pagerank: A context-sensitive ranking algorithm for web searchIEEE Transactions on Knowledge and Data Engineering, 2003
- Scaling personalized web searchPublished by Association for Computing Machinery (ACM) ,2003
- The mixing rate of Markov chains, an isoperimetric inequality, and computing the volumePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- How Good is Recursive Bisection?SIAM Journal on Scientific Computing, 1997
- Random walks in a convex body and an improved volume algorithmRandom Structures & Algorithms, 1993
- Conductance and convergence of Markov chains-a combinatorial treatment of expandersPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1988