A uniform approach to accelerated PageRank computation

ABSTRACT

In this note we consider a simple reformulation of the traditional power iteration algorithm for computing the stationary distribution of a Markov chain. Rather than communicate their current probability values to their neighbors at each step, nodes instead communicate only changes in probability value. This reformulation enables a large degree of flexibility in the manner in which nodes update their values, leading to an array of optimizations and features, including faster convergence, efficient incremental updating, and a robust distributed implementation.While the spirit of many of these optimizations appear in previous literature, we observe several cases where this unification simplifies previous work, removing technical complications and extending their range of applicability. We implement and measure the performance of several optimizations on a sizable (34M node) web subgraph, seeing significant composite performance gains, especially for the case of incremental recomputation after changes to the web graph.

REFERENCES

• 1: Arvind Arasu, Jasmine Novak, Andrew Tomkins, and John Tomlin, Pagerank computation and the structure of the web: Experiments and algorithms. WWW 2002 poster.
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 3: Steve Chien, Cynthia Dwork, Ravi Kumar, Dan Simon, and D. Sivakumar, Link evolution: Analysis and algorithms. Internet Mathematics: Volume 1, No. 3, pp. 277--304.
• 4: Nadav Eiron , Kevin S. McCurley , John A. Tomlin, Ranking the web frontier, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988714]
• 5: Sepandar Kamvar, Taher Haveliwala, and Gene Golub, Adaptive Methods for the Computation of PageRank. Stanford University Technical Report, 2003.
• 6: Sepandar Kamvar, Taher Haveliwala, Christopher Manning, and Gene Golub, Exploiting the Block Structure of the Web for Computing PageRank. Stanford University Technical Report, 2003.
• 7: Sepandar D. Kamvar , Taher H. Haveliwala , Christopher D. Manning , Gene H. Golub, Extrapolation methods for accelerating PageRank computations, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775190]
• 8: Taher H. Haveliwala, Topic-sensitive PageRank, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511513]
• 9: Glen Jeh , Jennifer Widom, Scaling personalized web search, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775191]
• 10: Amy Langville and Carl Meyer, A Reordering for the PageRank problem. NCSU CRSC Technical Report #CRSC-TR04-16. March 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
PageRank, link analysis, random walks, web graph