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 detection21. 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 (tk α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.
%0 Conference Paper
%1 boldi_pagerank_2005
%A Boldi, Paolo
%A Santini, Massimo
%A Vigna, Sebastiano
%B Proceedings of the 14th International Conference on World Wide Web
%C Chiba
%D 2005
%I ACM
%K relevance_ranking
%P 557--566
%R 10.1145/1060745.1060827
%T PageRank as a function of the damping factor
%U http://dx.doi.org/10.1145/1060745.1060827
%X 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 detection21. 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 (tk α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.
%@ 1-59593-046-9
@inproceedings{boldi_pagerank_2005,
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 (tk α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.},
added-at = {2018-11-04T16:54:56.000+0100},
address = {Chiba},
author = {Boldi, Paolo and Santini, Massimo and Vigna, Sebastiano},
biburl = {https://www.bibsonomy.org/bibtex/222f4e5867e709be8bde7b7e66a2de04b/lepsky},
booktitle = {Proceedings of the 14th {International} {Conference} on {World} {Wide} {Web}},
doi = {10.1145/1060745.1060827},
interhash = {35b314c06e470c543b6be694d282d9a2},
intrahash = {22f4e5867e709be8bde7b7e66a2de04b},
isbn = {1-59593-046-9},
keywords = {relevance_ranking},
note = {bibtex: Boldi2005PageRank},
pages = {557--566},
publisher = {ACM},
series = {{WWW} '05},
timestamp = {2018-11-07T09:17:29.000+0100},
title = {{PageRank} as a function of the damping factor},
url = {http://dx.doi.org/10.1145/1060745.1060827},
year = 2005
}