2026-07-25T00:40:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1072 2024-03-06T11:07:19Z ddc:004 open_access

A Deeper Investigation of PageRank as a Function of the Damping Factor Boldi, Paolo Santini, Massimo Vigna, Sebastiano PageRank damping factor Markov chains 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 $alpha$ that spreads uniformly part of the rank. The choice of $alpha$ is eminently empirical, and in most cases the original suggestion $alpha=0.85$ by Brin and Page is still used. In this paper, we give a mathematical analysis of PageRank when $alpha$ changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of $alpha$ close to $1$ do not give a more meaningful ranking. Then, we give closed-form formulae for PageRank derivatives of any order, and by proving that the $k$-th iteration of the Power Method gives exactly the PageRank value obtained using a Maclaurin polynomial of degree $k$, we show how to obtain an approximation of the derivatives. Finally, we view PageRank as a linear operator acting on the preference vector and show a tight connection between iterated computation and derivation. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paolo Boldi and Massimo Santini and Sebastiano Vigna 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 7071, Web Information Retrieval and Linear Algebra Algorithms (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.07071.3 urn:nbn:de:0030-drops-10722 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07071.3 eng https://creativecommons.org/licenses/by/4.0/legalcode