Local Graph Partitioning using PageRank Vectors

By Reid Andersen, Fan Chung Graham, Kevin J. Lang. 2006

1,111 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Electrical and Electronic Engineering, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Electrical and Electronic Engineering

In Graph Learning

Citations in the corpus

DeepWalk: online learning of social representations (2014, methodology): “Random walks have been used as a similarity measure for a variety of problems in content recommendation [11] and community detection [1].”
A Graph-Based Push Service Platform (2016, methodology): “Therefore we propose A-PARW in Algorithm 1 motivated by [1].”
Random walks and diffusion on networks (2016, methodology): “Nibble is a local community-detection algorithm based on DTRWs [365–367].”
Large-Scale Community Detection on YouTube for Topic Discovery and Exploration (2011, methodology): “This local partitioning algorithm based on evolving set has improved computational complexity over the best previous local partitioning algorithm by Andersen et al. (2006).”
Diffusion Improves Graph Learning (2019, methodology): “Most importantly, there are fast approximations for both PPR [3, 77] and the heat kernel [34], with which GDC achieves a linear runtimeO(N).”
Defining and evaluating network communities based on ground-truth (2012, methodology): “Moreover, the random work is “truncated” as it sets PageRank scores r u to 0 for nodes u with r u ε , for some small constant ε [2].”
Empirical comparison of algorithms for network community detection (2010, background): “For example in Figure 1(left), sets A and B have conductance φ ( A ) = > φ ( B ) = , so the set of nodes B is more community-like than the set A .”
A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning (2008, methodology): “By using the personal PageRank vector [PBMW98] to deﬁne nearness, Andersen, Chung and Lang [ACL06], have produced an improved version of our algorithm Nibble , which they call PageRank-Nibble .”
Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals (2021, neutral): “ing [30, 31], we use the topic entities labeled in original datasets and adopt PageRank-Nibble algorithm (PRN) [1] to find KB entities close to them.”
Handbook of Big Data (2016, methodology): “∗That being said, this does not mean that the näıve cubic algorithm is best, for example, faster algorithms that have been developed for much larger graphs can implicitly regularize against noise in the graph [31,32].”
IsoRankN: spectral methods for global alignment of multiple protein networks (2009, methodology): “Anderson et al. (2006) showed that a low-conductance set containing v can be computed efficiently via the personalized PageRank vector of v.”
Scaling Graph Neural Networks with Approximate PageRank (2020, methodology): “vertheless, we can obtain a good approximation by truncating small elements to zero since most of the probability mass in the personalized PageRank vectors π(i)is localized on a small number of nodes [5, 23, 36]. Thus, we can approximate π(i)with a sparse vector and in turn approximate Πppr with a s”
Maximizing Social Influence in Nearly Optimal Time (2012, background): “The influence estimation problem shares some commonality with the problems of local graph partitioning, as well as estimating pagerank and personalized pagerank vectors [1, 6, 37, 2].”
The heat kernel as the pagerank of a graph (2007, methodology): “By using PageRank, an improved local partitioning algorithm was given in [1, 2].”
Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, background): “One can thus find nodes tightly coupled to i, a feature that can be employed for local community detection [6,79] and graph-based semi-supervised learning [60].”
Sybil Attacks and Their Defenses in the Internet of Things (2014, methodology): “Leveraging the " social network " structure, Yu et al. [24] propose a famous SNSD scheme, SybilGuard, based on random walk [48], [49].”