Learn Before
Theory

Local Graph Partitioning using PageRank Vectors (Andersen, Chung, Lang, 2006)

Local Graph Partitioning using PageRank Vectors (Andersen, Chung, and Lang, FOCS 2006) is a local clustering algorithm based on approximate personalized PageRank (APPR). Starting from a single seed vertex vv, the method computes a sparse approximation of the personalized PageRank vector with teleport distribution concentrated on vv using an incremental push operation, and then performs a sweep over vertices ordered by approximate PageRank score divided by degree to extract a low-conductance cut. Two key properties make the procedure local. First, the push computation touches only vertices in (or near) the eventual cluster, so its running time is bounded essentially in terms of the cluster size rather than the size of the whole graph. Second, the algorithm offers a Cheeger-style conductance guarantee: if a set SS of low conductance contains the seed, a sweep over the APPR vector recovers a set with conductance O(ϕ(S)logS)O(\sqrt{\phi(S) \log |S|}). The construction is the canonical seeded PageRank-style diffusion used to identify local cluster structure without globally analyzing the graph.

0

1

Updated 2026-05-16

Contributors are:

Who are from:

Tags

Science