Efficient algorithms for Personalized PageRank
Abstract/Contents
- Abstract
- 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.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2015 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Lofgren, Peter Andrew |
|---|---|
| Associated with | Stanford University, Department of Computer Science. |
| Primary advisor | Garcia-Molina, Hector |
| Primary advisor | Goel, Ashish |
| Thesis advisor | Garcia-Molina, Hector |
| Thesis advisor | Goel, Ashish |
| Thesis advisor | Leskovec, Jurij |
| Advisor | Leskovec, Jurij |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Peter Andrew Lofgren. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2015. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2015 by Peter Andrew Lofgren
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...