PageRank as a function of the damping factor
PageRank as a function of the damping factor
复制标题
DOI：
10.1145/1060745.1060827
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
P. Boldi;Massimo Santini;S. Vigna
中科院分区：
文献类型：
--
作者：
P. Boldi;Massimo Santini;S. Vigna
PageRank被定义为马尔可夫链的平稳状态。该链通过扰动由具有均匀分布部分秩的阻尼因子α的网络图诱导的转移矩阵来获得。α的选择显然是经验性的，在大多数情况下，布林和佩奇最初的建议α = 0.85仍然被使用。然而，最近，PageRank相对于α变化的行为被发现在垃圾链接检测中很有用[21]。此外，仍然缺少α值选择的分析依据。本文首次给出了PageRank在α变化时的数学分析。特别是，我们表明，与流行的信念相反，对于现实世界的图，α值接近1并没有给出更有意义的排名。然后，我们给出了任何阶PageRank导数的封闭形式公式，以及幂方法的一个扩展，该方法对k阶导数的收敛性为O（tk α t）。最后，我们证明了迭代计算和分析行为之间的紧密联系，第k次迭代的功率方法给出了精确的PageRank值使用麦克劳林多项式的k度。后者的结果铺平了道路的应用分析方法的研究PageRank。
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.