Efficient algorithms for Personalized PageRank
- We present new, more efficient algorithms for estimating random walk scores such as Personalized PageRank from a given source node to one or several target nodes. These scores are useful for personalized search and recommendations on networks including social networks, user-item networks, and the web. Past work has proposed using Monte Carlo or using linear algebra to estimate scores from a single source to every target, making them inefficient for a single pair. Our contribution is a new bidirectional algorithm which combines linear algebra and Monte Carlo to achieve significant speed improvements. On a diverse set of six graphs, our algorithm is 70x faster than past state-of-the-art algorithms. We also present theoretical analysis: while past algorithms require Omega(n) time to estimate a random walk score of typical size 1/n on an n-node graph to a given constant accuracy, our algorithm requires only O(m) expected time for an average target, where m is the number of edges, and is provably accurate. In addition to our core bidirectional estimator for personalized PageRank, we present an alternative algorithm for undirected graphs, a generalization to arbitrary walk lengths and Markov Chains, an algorithm for personalized search ranking, and an algorithm for sampling random paths from a given source to a given set of targets. We expect our bidirectional methods can be extended in other ways and will be useful subroutines in other graph analysis problems.
|Type of resource
|electronic; electronic resource; remote
|1 online resource.
|Lofgren, Peter Andrew
|Stanford University, Department of Computer Science.
|Statement of responsibility
|Peter Andrew Lofgren.
|Submitted to the Department of Computer Science.
|Thesis (Ph.D.)--Stanford University, 2015.
- © 2015 by Peter Andrew Lofgren
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...