AN INNER-OUTER ITERATION FOR COMPUTING PAGERANK

被引：77

作者：

Gleich, David F. ^{[1
]}

Gray, Andrew P. ^{[2
]}

Greif, Chen ^{[3
]}

Lau, Tracy ^{[3
]}

机构：

[1] Stanford Univ, Inst Computat & Math Engn, Stanford, CA 94305 USA

[2] Univ British Columbia, Fac Med, Vancouver, BC V6T 1Z3, Canada

[3] Univ British Columbia, Dept Comp Sci, Vancouver, BC V6T 1Z4, Canada

来源：

SIAM JOURNAL ON SCIENTIFIC COMPUTING | 2010年 / 32卷 / 01期

关键词：

damping factor; eigenvalues; inner-outer iterations; PageRank; power method; stationary schemes; KRYLOV SUBSPACE METHODS; INEXACT; EIGENVECTOR; ALGORITHM; GOOGLE; WEB;

D O I：

10.1137/080727397

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present a new iterative scheme for PageRank computation. The algorithm is applied to the linear system formulation of the problem, using inner-outer stationary iterations. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Our convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not sensitive to the choice of the parameters involved. The same idea can be used as a preconditioning technique for nonstationary schemes. Numerical examples featuring matrices of dimensions exceeding 100,000,000 in sequential and parallel environments demonstrate the merits of our technique. Our code is available online for viewing and testing, along with several large scale examples.

引用

页码：349 / 371

页数：23

共 46 条

[1]

[Anonymous], P WSDM 2009 ACM NEW

[2]

[Anonymous], 1994, ITERATIVE SOLUTION L

[3]

[Anonymous], 2005, P 14 INT C WORLD WID, DOI 10.1145/1060745.1060827

[4]

[Anonymous], LIB C SUBJ HEAD

[5]

[Anonymous], 2006, Google's PageRank and beyond: the science of search engine rankings

[6]

[Anonymous], 1994, CLASSICS APPL MATH

[7]

[Anonymous], 1962, Matrix Iterative Analysis

[8]

[Anonymous], 1994, Introduction to the Numerical Solutions of Markov Chains

[9]

[Anonymous], P 22 INT C MACH LEAR

[10]

[Anonymous], P 11 INT WORLD WID W

← 1 2 3 4 5 →