On convergence of the inner-outer iteration method       for computing PageRank

Zhong-Zhi Bai

doi:10.3934/naco.2012.2.855

Article Contents

2012, Volume 2, Issue 4: 855-862. Doi: 10.3934/naco.2012.2.855

This issue Previous Article Newton-MHSS methods for solving systems of nonlinear equations with complex symmetric Jacobian matrices Next Article On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems

On convergence of the inner-outer iteration method for computing PageRank

Zhong-Zhi Bai^1,

1.
School of Mathematics and Computer Science, Guizhou Normal University, Guiyang 550001

Received: December 31, 2011

Revised: September 30, 2012

Published: October 2012

Abstract Related Papers Cited by

Abstract

Without imposing any restriction on the damping factors and the stopping tolerances, we prove the overall convergence of the inner-outer iteration method for computing the PageRank vector, which was proposed by Gleich, Gray, Greif and Lau (SIAM J. Sci. Comput. 32(2010)349-371). Based on the formula of the contraction factor of the method, we discuss possible choices of the iteration parameters, which could be practically useful for accelerating the convergence rate of the inner-outer iteration method.

Keywords:

Mathematics Subject Classification: Primary: 65F10, 65F15; Secondary: 65C40.

Citation:

Related Papers

Cited by

References

[1]	Z. -Z. Bai, J. -C. Sun and D. -R. Wang, A unified framework for the construction of various matrix multisplitting iterative methods for large sparse system of linear equations, Computers Math. Appl., 32 (1996), 51-76.doi: 10.1016/S0898-1221(96)00207-6.
[2]	P. Berkhin, A survey on PageRank computing, Internet Math., 2 (2005), 73-120.doi: 10.1080/15427951.2005.10129098.
[3]	A. N. Langville and C. D. Meyer, A survey of eigenvector methods for Web information retrieval, SIAM Rev., 47 (2005), 135-161.doi: 10.1137/S0036144503424786.
[4]	L. Page, S. Brin, R. Motwani and T. Winograd, "The PageRank Citation Ranking: Bringing Order to the Web," Stanford Digital Libraries SIDL-WP-1999-0120, Stanford, 1999.
[5]	D. F. Gleich, A. P. Gray, C. Greif and T. Lau, An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32 (2010), 349-371.doi: 10.1137/080727397.
[6]	J. -F. Yin, G. -J. Yin and M. K. Ng, On adaptively accelerated Arnoldi method for computing PageRank, Numer. Linear Algebra Appl., 19 (2012), 73-85.doi: 10.1002/nla.789.