An Arnoldi-Extrapolation algorithm for computing PageRank
An Arnoldi-Extrapolation algorithm for computing PageRank
复制标题
用于计算 PageRank 的 Arnoldi-Extrapolation 算法
DOI：
10.1016/j.cam.2010.02.009
复制
发表时间：
2010-10
影响因子：
2.4
通讯作者：
Wei, Yimin
中科院分区：
文献类型：
--
作者：
Wu, Gang;Wei, Yimin
Golub和Greif [G.戈卢布角Greif，An Arnoldi-type algorithm for computing PageRank，BIT 46（2006）759-771]是用于计算PageRank的重新开始的Krylov子空间方法。然而，当阻尼因子较高且搜索子空间维数较小时，该算法可能效率不高。在本文中，我们首先发展了一种基于里兹值的外推方法。然后，我们考虑如何定期编织这种外推方法与Arnoldi型算法。由此产生的算法是Arnoldi-Extrapolation算法。分析了新算法的收敛性。数值实验证明了该算法的数值性能。
The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759–771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.
登录
查看更多内容
DOI：
--
发表时间：
2003
期刊：
--
影响因子：
--
作者：
Taher H. Haveliwala;S. Kamvar
通讯作者：
Taher H. Haveliwala;S. Kamvar
影响因子：
--
作者：
Berkhin, Pavel
通讯作者：
Berkhin, Pavel
影响因子：
1.7
作者：
M. Crouzeix
通讯作者：
M. Crouzeix
DOI：
10.1145/1060745.1060827
发表时间：
2005-05
期刊：
--
影响因子：
--
作者：
P. Boldi;Massimo Santini;S. Vigna
通讯作者：
P. Boldi;Massimo Santini;S. Vigna
DOI：
10.1137/040619028
发表时间：
2005-12
期刊：
SIAM J. Matrix Anal. Appl.
影响因子：
--
作者：
A. Langville;C. D. Meyer
通讯作者：
A. Langville;C. D. Meyer