Learn Before
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 , the method computes a sparse approximation of the personalized PageRank vector with teleport distribution concentrated on 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 of low conductance contains the seed, a sweep over the APPR vector recovers a set with conductance . The construction is the canonical seeded PageRank-style diffusion used to identify local cluster structure without globally analyzing the graph.
0
1
Tags
Science