Skip to main content
SpringerLink
Log in

An Arnoldi-Inout method accelerated with a two-stage matrix splitting iteration for computing PageRank

  • Published:
Calcolo Aims and scope Submit manuscript

Abstract

The PageRank algorithm is one of the most commonly used techniques that determines the global importance of Web pages. In this paper, we present a preconditioned Arnoldi-Inout approach for the computation of Pagerank vector, which can take the advantage of both a new two-stage matrix splitting iteration and the Arnoldi process. The implementation and convergence of the new algorithm are discussed in detail. Numerical experiments are presented to illustrate the effectiveness of our approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Page, L., Brin, S., Motwani, R., Winograd, T.: The PageRank Citation Ranking: Bring Order to the Web, Stanford Digital Libraries Working Paper (1998)

  2. Golub, G.H., Van Loan, C.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)

    MATH  Google Scholar 

  3. Kamvar, S., Haveliwala, T., Manning, C., Golub, G.H.: Extrapolation methods for accelerating PageRank computations, in Twelfth International World Wide Web Conference, May 20–24. Budapest, Hungary (2003)

  4. Langville, A., Meyer, C.: Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press, Princeton (2006)

    MATH  Google Scholar 

  5. Kamvar, S., Haveliwala, T.: The Condition Number of the PageRank Problem, Technical report, Stanford University, Stanford, CA, 2003, http://dbpubs.stanford.edu:8090/pub/2003-36

  6. Haveliwala, T., Kamvar, S.: The second eigenvalue of the Google matrix. In: Proceedings of the Twelfth International World Wide Web of Conference (2003)

  7. Wu, G., Wei, Y.-M.: An Arnoldi-extrapolation algorithm for computing PageRank. J. Comput. Appl. Math. 234, 3196–3212 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  8. Meyer, C.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000)

    Book  Google Scholar 

  9. Langville, A., Meyer, C.: Deeper inside PageRank. Internet Math. 1, 335–380 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gleich, D., Gray, A., Greif, C., Lau, T.: An inner-outer iteration for computing PageRank. SIAM J. Sci. Comput. 32, 349–371 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gu, C.-Q., Xie, F., Zhang, K.: A two-step matrix splitting iteration for computing PageRank. J. Comput. Appl. Math. 278, 19–28 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bai, Z.-Z.: On convergence of the inner-outer iteration method for computing PageRank. Numer. Algebra Control Optim. 2, 855–862 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gu, C.-Q., Wang, W.-W.: An Arnoldi-Inout algorithm for computing PageRank problems. J. Comput. Appl. Math. 309, 219–229 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  14. Gu, C.-Q., Wang, L.: On the multi-splitting iteration method for computing PageRank. J. Appl. Math. Comput. 42, 479–490 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  15. Golub, G.H., Greif, C.: An Arnoldi-type algorithm for computing PageRank. BIT 46, 759–771 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Jia, Z.-X.: Refined iterative algorithms based on Arnoldi’s process for large unsymmetric eigenproblems. Linear Algebra Appl. 259, 1–23 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  17. Wu, G., Wei, Y.-M.: A Power-Arnoldi algorithm for computing PageRank. Numer. Linear Algebra Appl. 14, 521–546 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  18. Wu, K.-S., Simon, H.: Thick-restart Lanczos method for large symmetric eigenvalue problems. SIAM J. Matrix Anal. Appl. 22, 602–616 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  19. Morgan, R., Zeng, M.: A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity. Linear Algebra Appl. 415, 96–113 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  20. Sorensen, D.: Implicit application of polynomial filters in a \(k-\)step Arnoldi method. SIAM J. Matrix Anal. Appl. 13, 357–385 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  21. Wu, G., Zhang, Y., Wei, Y.-M.: Accelerating the Arnoldi-Type Algorithm for the PageRank Problem and the ProteinRank Problem. J. Sci. Comput. 57, 74–104 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  22. Brezinski, C., Redivo-Zaglia, M.: Rational extrapolation for the PageRank vector. Math. Comput. 77, 1585–1598 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  23. Sidi, A.: Vector extrapolation methods with applications to solution of large systems of equations and to PageRank computations. Comput. Math. Appl. 56, 1–24 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  24. Smith, D.A., Ford, W.F., Sidi, A.: Extrapolation methods for vector sequences. SIAM Rev. 29, 199–233 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  25. Pu, B.-Y., Huang, T.-Z., Wen, C.: A preconditioned and extrapolation-accelerated GMRES method for PageRank. Appl. Math. Lett. 37, 95–100 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. Zhang, H.-F., Huang, T.-Z., Wen, C., et al.: FOM accelerated by an extrapolation method for solving PageRank problems. J. Comput. Appl. Math. 296, 397–409 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ipsen, I., Kirkland, S.: Convergence analysis of a PageRank updating algorithm by Langville and Meyer. SIAM J. Matrix Anal. Appl. 27, 952–967 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  28. Langville, A., Meyer, C.: Updating markov chains with an eye on Google’s PageRank. SIAM J. Matrix Anal. Appl. 27, 968–987 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  29. Ipsen, I., Selee, T.: PageRank computation with special attention to dangling nodes. SIAM J. Matrix Anal. Appl. 29, 1281–1296 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  30. Berkhin, P.: A survey on PageRank computing. Internet Math. 2, 73–120 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  31. Wu, G., Wei, Y.-M.: Arnoldi versus GMRES for computing PageRank: a theoretical contribution to Google’s PageRank problem. ACM Trans. Inf. Syst. 28, 1–28 (2010)

    Article  Google Scholar 

  32. Bianchini, M., Gori, M., Scarselli, F.: Inside PageRank. ACM Trans. Internet Technol. 5, 92–128 (2005)

    Article  Google Scholar 

  33. Peaceman, D.W., Rachford Jr., H.H.: The numerical solution of parabolic and elliptic differential equations. J. Soc. Ind. Appl. Math. 3, 28–41 (1955)

    Article  MathSciNet  MATH  Google Scholar 

  34. Bai, Z.-Z., Golub, G.H., Ng, M.K.: Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems. SIAM J. Matrix. Anal. Appl. 24, 603–626 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  35. Bai, Z.-Z., Golub, G.H., Lu, L.-Z., Yin, J.-F.: Block triangular and skew-Hermitian splitting methods for positive-definite linear systems. SIAM J. Sci. Comput. 26, 844–863 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  36. Bai, Z.-Z.: A class of two-stage iterative methods for systems of weakly nonlinear equations. Numer. Algorithms 14, 295–319 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  37. Bai, Z.-Z., Wang, D.-R.: The monotone convergence of the two-stage iterative method for solving large sparse systems of linear equations. Appl. Math. Lett. 10, 113–117 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  38. Saad, Y.: Numerical Methods for Large Eigenvalue Problems, Algorithms and Architectures for Advanced Scientific Computing. Manchester University Press, Manchester (1992)

    Google Scholar 

  39. Saad, Y.: Chebyshev acceleration techniques for solving nonsymmetric eigenvalue problems. Math. Comp. 42, 567–588 (1984)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to acknowledge the anonymous referees who suggested a number of useful improvements.

Author information

Authors and Affiliations

  1. Department of Mathematics, Shanghai University, Shanghai, 200444, China

    Yongxin Dong & Chuanqing Gu

  2. School of Mathematics and Statistics, Shenzhen University, Shenzhen, 518052, China

    Zhibing Chen

Authors
  1. Yongxin Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chuanqing Gu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Zhibing Chen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Chuanqing Gu.

Additional information

The work are supported by National Natural Science Foundation (11371243), Innovation Program of Shanghai Municipal Education Commission (13ZZ068), Key Disciplines of Shanghai Municipality (S30104), The Grant of Shanghai Science and Technology Commission (13521101202).

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Dong, Y., Gu, C. & Chen, Z. An Arnoldi-Inout method accelerated with a two-stage matrix splitting iteration for computing PageRank. Calcolo 54, 857–879 (2017). https://doi.org/10.1007/s10092-016-0211-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10092-016-0211-2

Keywords

Mathematics Subject Classification

Search

Navigation