中文

Journal of Shanghai University >

2017 , Vol. 23 >Issue 4: 555 - 562

DOI: https://doi.org/10.12066/j.issn.1007-2861.1867

Arnoldi-PIO algorithm for PageRank

Expand
  • 1. College of Sciences, Shanghai University, Shanghai 200444, China;
    2. Science and Technology on Communication Security Laboratory, Chengdu 610041, China

Received date: 2016-10-13

  Online published: 2017-08-30

Fold

Abstract

The PageRank algorithm plays an important role in determining the importance of Web pages. The power-inner-outer (PIO) method is a two-step splitting iteration framework that combines the inner-outer scheme with the classical power method to accelerate the computation of PageRank algorithm. This paper proposes an Arnoldi-PIO algorithm, which is a PIO iteration algorithm modified with the thick restarted Arnoldi method. Description and convergence of the proposed algorithm are discussed in details. Numerical results show efficiency and convergence behaviors of the algorithm.

Key words： thick restarted Arnoldi algorithm; two-step splitting iteration; inner-outer iteration

Cite this article

GU Chuanqing1, NIE Ying1, WANG Jinbo2 . Arnoldi-PIO algorithm for PageRank[J]. Journal of Shanghai University, 2017 , 23(4) : 555 -562 . DOI: 10.12066/j.issn.1007-2861.1867

References

[1] Page L, Brin S, Motwani R, et al. The PageRank citation ranking: bring order to the web [R/OL]. (2001-10-30)[2014-06-20]. http://ilpubs.stanford.edu:8090/422/1/1999-66.pdf.
[2] Gleich D, Gray A, Greif C, et al. An inner-outer iteration method for computing PageRank [J]. SIAM J Sci Compute, 2010, 32(1): 349-371.
[3] Gu C Q, Xie F, Zhang K. A two-step splitting iteration for computing PageRank [J]. Journal of Computational and Applied Mathematics, 2015, 278: 19-28.
[4] Wu G, Wei Y M. A Power-Arnoldi algorithm for compuring PageRank [J]. Numer Linear Algebra Appl, 2007, 14: 521-546.
[5] Wu K, Simon H. Thick-restart Lanczos method for large symmetric eigenvalue problems [J]. SIAM Journal on Matrix Analysis and Applications, 2000, 22: 602-616.
[6] Morgan R. A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determing multiplicity [J]. Linear Algebra and Its Applications, 2006, 415: 96-113.
[7] Sorensen D. Implicit application of polynomial filters in a k-step Arnoldi method [J]. SIAM Journal on Matrix Analysis and Applications, 1992, 13: 357-385.

Options
Outlines

/

〈 〉