PageRank as a function of the damping factor

ABSTRACT

PageRank is defined as the stationary state of a Markov chain. The chain is obtained by perturbing the transition matrix induced by a web graph with a damping factor α that spreads uniformly part of the rank. The choice of α is eminently empirical, and in most cases the original suggestion α = 0.85 by Brin and Page is still used. Recently, however, the behaviour of PageRank with respect to changes in α was discovered to be useful in link-spam detection[21]. Moreover, an analytical justification of the value chosen for α is still missing. In this paper, we give the first mathematical analysis of PageRank when α changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of α close to 1 do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and an extension of the Power Method that approximates them with convergence O (t^k α^t) for the k-th derivative. Finally, we show a tight connection between iterated computation and analytical behaviour by proving that the k-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree k. The latter result paves the way towards the application of analytical methods to the study of PageRank.

REFERENCES

• 1: Paolo Boldi , Bruno Codenotti , Massimo Santini , Sebastiano Vigna, UbiCrawler: a scalable fully distributed web crawler, Software—Practice & Experience, v.34 n.8, p.711-726, 10 July 2004 [doi>10.1002/spe.587]
• 2: P. Boldi , S. Vigna, The webgraph framework I: compression techniques, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988752]
• 3: Soumen Chakrabarti, Byron Dom, David Gibson, Jon Kleinberg, S. Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, and Andrew Tomkins. Hypersearching the web. Scientific American, June 1999.
• 4: Scott C. Deerwester, Susan T. Dumais, Thomas K. Landauer, George W. Furnas, and Richard A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 5: 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]
• 6: Gene H. Golub and Chen Greif. Arnoldi-type algorithms for computing stationary distribution vectors, with application to PageRank. Technical Report SCCM-04-15, Stanford University Technical Report, 2004.
• 7: Taher Haveliwala. Efficient computation of PageRank. Technical report, Stanford University Technical Report, October 1999.
• 8: Taher Haveliwala and Sepandar Kamvar. The condition number of the PageRank problem. Technical Report~36, Stanford University Technical Report, June 2003.
• 9: Taher Haveliwala and Sepandar Kamvar. The second eigenvalue of the Google matrix. Technical Report~20, Stanford University Technical Report, March 2003.
• 10: Sepandar Kamvar, Taher Haveliwala, Christopher Manning, and Gene Golub. Exploiting the block structure of the web for computing PageRank. Technical Report 17, Stanford University Technical Report, March 2003.
• 11: 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]
• 12: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 13: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , D. Sivakumar , Andrew Tompkins , Eli Upfal, The Web as a graph, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-10, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335170]
• 14: Amy N. Langville and Carl D. Meyer. Deeper inside PageRank. Internet Mathematics, 1(3):355--400, 2004.
• 15: Chris Pan-Chi Lee, Gene H. Golub, and Stefanos A. Zenios. A fast two-stage algorithm for computing PageRank and its extensions. Technical report, Stanford University Technical Report, 2004.
• 16: R. Lempel , S. Moran, SALSA: the stochastic approach for link-structure analysis, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.131-160, April 2001 [doi>10.1145/382979.383041]
• 17: Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, Stanford University, Stanford, CA, USA, 1998.
• 18: Luca Pretto, A Theoretical Analysis of Google's PageRank, Proceedings of the 9th International Symposium on String Processing and Information Retrieval, p.131-144, September 11-13, 2002
• 19: Luca Pretto. A theoretical approach to link analysis algorithms, 2002. PhD Thesis.
• 20: Eugene Seneta. Non-Negative Matrices and Markov Chains. Springer Series in Statistics. Springer-Verlag, 1981.
• 21: Hui Zhang, Ashish Goel, Ramesh Govindan, Kahn Mason, and Benjamin~Van Roy. Making eigenvector-based reputation systems robust to collusion. In Stefano Leonardi, editor, Proceedings WAW 2004, number 3243 in LNCS, pages 92--104. Springer-Verlag, 2004.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Experimentation, Measurement

Keywords:
PageRank, Web graph, approximation