PageRank: functional dependencies

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 \u3b1 that spreads uniformly part of the rank. The choice of \u3b1 is eminently empirical, and in most cases the original suggestion \u3b1=0.85 by Brin and Page is still used. In this paper, we give a mathematical analysis of PageRank when \u3b1 changes. In particular, we show that, contrarily to popular belief, for real-world graphs values of \u3b1 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 value obtained by truncating the PageRank power series at 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