Boldi, Paolo ;
Santini, Massimo ;
Vigna, Sebastiano
A Deeper Investigation of 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 $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 realworld graphs values of $alpha$ close to $1$ do not give a more
meaningful ranking. Then, we give closedform 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.
BibTeX  Entry
@InProceedings{boldi_et_al:DSP:2007:1072,
author = {Paolo Boldi and Massimo Santini and Sebastiano Vigna},
title = {A Deeper Investigation of PageRank as a Function of the Damping Factor},
booktitle = {Web Information Retrieval and Linear Algebra Algorithms},
year = {2007},
editor = {Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
number = {07071},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Internationales Begegnungs und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2007/1072},
annote = {Keywords: PageRank, damping factor, Markov chains}
}
Keywords: 

PageRank, damping factor, Markov chains 
Seminar: 

07071  Web Information Retrieval and Linear Algebra Algorithms

Issue date: 

2007 
Date of publication: 

28.06.2007 