2014 FASTPPRScalingPersonalizedPager

• (Lofgren et al., 2014) ⇒ Peter A. Lofgren, Siddhartha Banerjee, Ashish Goel, and C. Seshadhri. (2014). “FAST-PPR: Scaling Personalized Pagerank Estimation for Large Graphs.” In: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2014) Journal. ISBN:978-1-4503-2956-9 doi:10.1145/2623330.2623745

Subject Headings:

Cited By

• http://scholar.google.com/scholar?q=%222014%22+FAST-PPR%3A+Scaling+Personalized+Pagerank+Estimation+for+Large+Graphs
• http://dl.acm.org/citation.cfm?id=2623330.2623745&preflayout=flat#citedby

Quotes

Author Keywords

• Computations on discrete structures; graph algorithms; personalized pagerank; social search

Abstract

We propose a new algorithm, FAST-PPR, for computing personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, it computes the Personalized PageRank π_s (t) from s to t, guaranteeing that the relative error is small as long π _s (t) > δ. Existing algorithms for this problem have a running-time of Î © (1/δ in comparison, FAST-PPR has a provable average running-time guarantee of O (√ d / δ) (where d is the average in-degree of the graph). This is a significant improvement, since δ is often O (1 / n) (where n is the number of nodes) for applications. We also complement the algorithm with an Î © (1/√δ) lower bound for PageRank estimation, showing that the dependence on δ cannot be improved.

We perform a detailed empirical study on numerous massive graphs, showing that FAST-PPR dramatically outperforms existing algorithms. For example, on the 2010 Twitter graph with 1.5 billion edges, for target nodes sampled by popularity, FAST-PPR has a 20 factor speedup over the state of the art. Furthermore, an enhanced version of FAST-PPR has a 160 factor speedup on the Twitter graph, and is at least 20 times faster on all our candidate graphs.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2014 FASTPPRScalingPersonalizedPager	C. Seshadhri Peter A. Lofgren Siddhartha Banerjee Ashish Goel			FAST-PPR: Scaling Personalized Pagerank Estimation for Large Graphs				10.1145/2623330.2623745		2014