License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.07071.3
URN: urn:nbn:de:0030-drops-10722
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2007/1072/
Go to the corresponding Portal

Boldi, Paolo ; Santini, Massimo ; Vigna, Sebastiano

A Deeper Investigation of PageRank as a Function of the Damping Factor

pdf-format:
07071.VignaSebastiano.Paper.1072.pdf (0.4 MB)

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 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.

BibTeX - Entry

@InProceedings{boldi_et_al:DagSemProc.07071.3,
  author =	{Boldi, Paolo and Santini, Massimo and Vigna, Sebastiano},
  title =	{{A Deeper Investigation of PageRank as a Function of the Damping Factor}},
  booktitle =	{Web Information Retrieval and Linear Algebra Algorithms},
  pages =	{1--19},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{7071},
  editor =	{Andreas Frommer and Michael W. Mahoney and Daniel B. Szyld},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/1072},
  URN =		{urn:nbn:de:0030-drops-10722},
  doi =		{10.4230/DagSemProc.07071.3},
  annote =	{Keywords: PageRank, damping factor, Markov chains}
}

Keywords: PageRank, damping factor, Markov chains
Collection: 07071 - Web Information Retrieval and Linear Algebra Algorithms
Issue Date: 2007
Date of publication: 28.06.2007

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI