Acceleration of an adaptive generalized Arnoldi method for computing PageRank

Chun Wen; Qian-Ying Hu; Bing-Yuan Pu; Yu-Yun Huang; Chun Wen; Qian-Ying Hu; Bing-Yuan Pu; Yu-Yun Huang

doi:10.3934/math.2021053

AIMS Mathematics

2021, Volume 6, Issue 1: 893-907. doi: 10.3934/math.2021053

Previous Article Next Article

Research article

Acceleration of an adaptive generalized Arnoldi method for computing PageRank

1.
School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu, 610054, China
2.
School of Mathematical Sciences, Guizhou Normal University, Guiyang, 550025, China
3.
Department of Basic Courses, Chengdu Textile College, Chengdu, 611731, China
4.
School of Economic Mathematics, Southwestern University of Finance and Economics, Chengdu, 611130, China

Received: 01 September 2020 Accepted: 29 October 2020 Published: 04 November 2020
MSC : 65F15, 65F10

By considering a weighted inner product, an adaptive generalized Arnoldi (GArnoldi) method was constructed by ^[13] for computing PageRank. In order to accelerate the adaptive GArnoldi method, this paper proposes a new method by using the power method with extrapolation process based on Google matrix's trace (PET) as an accelerated technique of the adaptive GArnoldi method. The new method is called as GArnoldi-PET method, whose implementation and convergence analysis are discussed in detail. Numerical experiments are used to illustrate the effectiveness of our proposed method.
- PageRank,
- generalized Arnoldi method,
- extrapolation,
- power method
Citation: Chun Wen, Qian-Ying Hu, Bing-Yuan Pu, Yu-Yun Huang. Acceleration of an adaptive generalized Arnoldi method for computing PageRank[J]. AIMS Mathematics, 2021, 6(1): 893-907. doi: 10.3934/math.2021053

Related Papers:

Abstract

By considering a weighted inner product, an adaptive generalized Arnoldi (GArnoldi) method was constructed by ^[13] for computing PageRank. In order to accelerate the adaptive GArnoldi method, this paper proposes a new method by using the power method with extrapolation process based on Google matrix's trace (PET) as an accelerated technique of the adaptive GArnoldi method. The new method is called as GArnoldi-PET method, whose implementation and convergence analysis are discussed in detail. Numerical experiments are used to illustrate the effectiveness of our proposed method.

References

[1]	L. Page, S. Brin, R. Motwami, T. Winograd, The PageRank citation ranking: Bringing order to the web, Technical report, Computer Science Department, Stanford University, Stanford, CA, 1999.
[2]	S. Kamvar, T. Haveliwala, C. Manning, G. H. Golub, Exploiting the block structure of the web for computing PageRank, Technical Report, SCCM-03-02, Stanford University, 2003.
[3]	G. H. Golub, C. F. Van Loan, Matrix Computations, third ed., The Johns Hopkins University Press, Baltimore, London, 1996.
[4]	D. Gleich, A. Gray, C. Greif, T. Lau, An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32 (2010), 349-371. doi: 10.1137/080727397
[5]	Z. L. Tian, Y. Liu, Y. Zhang, Z. Y. Liu, M. Y. Tian, The general inner-outer iteration method based on regular splittings for the PageRank problem, Appl. Math. Comput., 356 (2019), 479-501.
[6]	X. Y. Tan, A new extrapolation method for pagerank computations, J. Comput. Appl. Math., 313 (2017), 383-392. doi: 10.1016/j.cam.2016.08.034
[7]	G. H. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT., 46 (2006), 759-771. doi: 10.1007/s10543-006-0091-y
[8]	G. Wu, Y. Wei, A Power-Arnoldi algorithm for computing pagerank, Numer. Linear Algebra Appl., 14 (2007), 521-546. doi: 10.1002/nla.531
[9]	R. Morgan, M. Zheng, A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl., 415 (2006), 96-113. doi: 10.1016/j.laa.2005.07.024
[10]	Q. Y. Hu, C. Wen, T. Z. Huang, Z. L. Shen, X. M. Gu, A variant of the Power-Arnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 381 (2021), 113034. doi: 10.1016/j.cam.2020.113034
[11]	A. Essai, Weighted FOM and GMRES for solving nonsymmetric linear systems, Numer. Algorithms, 18 (1998), 277-292. doi: 10.1023/A:1019177600806
[12]	H. S. Najafi, H. Ghazvini, Weighted restarting method in the weighted Arnoldi algorithm for computing the eigenvalues of a nonsymmetric matrix, Appl. Math. Comput., 175 (2006), 1276-1287.
[13]	J. F. Yin, G. J. Yin, M. Ng, On adaptively accelerated Arnoldi method for computing PageRank, Numer. Linear Algebra Appl., 19 (2012), 73-85. doi: 10.1002/nla.789
[14]	C. Wen, Q. Y. Hu, G. J. Yin, X. M. Gu, Z. L. Shen, An adaptive Power-GArnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 386 (2021), 113209. doi: 10.1016/j.cam.2020.113209
[15]	Z. X. Jia, Refined iterative algorithms based on Arnoldi's process for large unsymmetric eigenproblems, Linear Algebra Appl., 259 (1997), 1-23. doi: 10.1016/S0024-3795(96)00238-8
[16]	A. Langville, C. Meyer, Googles PageRank and Beyond: The Science of the Search Engine Rankings, Princeton University Press, 2006.
[17]	T. Haveliwala, S. Kamvar, The second eigenvalue of the google matrix, in: Proceedings of the Twelfth International World Wide Web of Conference, 2003.
[18]	F. Tudisco, C. Di Fiore, A preconditioning approach to the PageRank computation problem, Linear Algebra Appl., 435 (2011), 2222-2246.
[19]	S. Cipolla, C. Di Fiore, F. Tudisco, Euler-Richardson method preconditioned by weakly stochastic matrix algebras: A potential contribution to Pagerank computation, Electronic J. Linear Al., 32 (2017), 254-272. doi: 10.13001/1081-3810.3343
[20]	G. Wu, Y. C. Wang, X. Q. Jin, A preconditioned and shifted GMRES algorithm for the PageRank problem with multiple damping factors, SIAM J. Sci. Comput., 34 (2012), 2558-2575. doi: 10.1137/110834585

Reader Comments

Your name:*

Email:*
© 2021 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)