An Arnoldi-type algorithm for computing page rank

被引：97
作者：
Golub, G. H.
Greif, C.
机构：
[1] Stanford Univ, SCCM Program, Stanford, CA 94305 USA
[2] Univ British Columbia, Dept Comp Sci, Vancouver, BC V6T 1Z4, Canada
来源：
BIT NUMERICAL MATHEMATICS | 2006年 / 46卷 / 04期
关键词：
PageRank; power method; Arnoldi method; refined Arnoldi; singular value decomposition;
D O I：
10.1007/s10543-006-0091-y
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
We consider the problem of computing PageRank. The matrix involved is large and cannot be factored, and hence techniques based on matrix-vector products must be applied. A variant of the restarted refined Arnoldi method is proposed, which does not involve Ritz value computations. Numerical examples illustrate the performance and convergence behavior of the algorithm.
引用
收藏
页码：759 / 771
页数：13
相关论文
共 30 条
[1]  
[Anonymous], P 22 INT C MACH LEAR
[2]  
[Anonymous], 2003, ITERATIVE METHODS SP, DOI DOI 10.1137/1.9780898718003
[3]   THE PRINCIPLE OF MINIMIZED ITERATIONS IN THE SOLUTION OF THE MATRIX EIGENVALUE PROBLEM [J].
ARNOLDI, WE .
QUARTERLY OF APPLIED MATHEMATICS, 1951, 9 (01) :17-29
[4]  
Berman A., 1994, CLASSICS APPL MATH, DOI [10.1016/C2013-0-10361-3, 10.1137/1.9781611971262, DOI 10.1137/1.9781611971262]
[5]  
Bianchini M., 2005, ACM Transactions on Internet Technology, V5, P92, DOI 10.1145/1052934.1052938
[6]  
Boldi P., 2005, P 14 INT WORLD WID W, P557, DOI [10.1145/1060745.1060827, DOI 10.1145/1060745.1060827]
[7]  
Demmel JW., 1997, APPL NUMERICAL LINEA
[8]  
ELDEN L, 2003, LITHMATR0401 LINK U
[9]   SENSITIVITY OF THE STATIONARY DISTRIBUTION VECTOR FOR AN ERGODIC MARKOV-CHAIN [J].
FUNDERLIC, RE ;
MEYER, CD .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1986, 76 :1-17
[10]  
Gleich D., YRL2004038
123