Adaptive methods for the computation of PageRank

被引：120

作者：

Kamvar, S

Haveliwala, T

Golub, G

机构：

[1] Stanford Univ, Stanford, CA 94305 USA

[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2004年 / 386卷

关键词：

PageRank; eigenvalue problem; Web matrix;

D O I：

10.1016/j.laa.2003.12.008

中图分类号：

O29 [应用数学];

学科分类号：

070104 [应用数学];

摘要：

We observe that the convergence patterns of pages in the PageRank algorithm have a non-uniform distribution. Specifically, many pages converge to their true PageRank quickly, while relatively few pages take a much longer time to converge. Furthermore, we observe that these slow-converging pages are generally those pages with high PageRank. We use this observation to devise a simple algorithm to speed up the computation of PageRank, in which the PageRank of pages that have converged are not recomputed at each iteration after convergence. This algorithm, which we call Adaptive PageRank, speeds up the computation of PageRank by nearly 30%. (C) 2004 Published by Elsevier Inc.

引用

页码：51 / 65

页数：15