FAST-PPR: Scaling Personalized PageRank Estimation for Large Graphs

author: Peter Lofgren, Computer Science Department, Stanford University
published: Oct. 7, 2014,   recorded: August 2014,   views: 1935
Categories

Slides

Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.
  Bibliography

Description

We propose a new algorithm, FAST-PPR, for estimating personalized PageRank: given start node s and target node t in a directed graph, and given a threshold δ, FAST-PPR estimates the Personalized PageRank πs(t) from s to t, guaranteeing a small relative error 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.

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: