×

zbMATH — the first resource for mathematics

A variant of the Power-Arnoldi algorithm for computing PageRank. (English) Zbl 1452.65068
Summary: For computing PageRank problems, a Power-Arnoldi algorithm is presented by periodically knitting the power method together with the thick restarted Arnoldi algorithm. In this paper, by using the power method with the extrapolation process based on trace (PET), a variant of the Power-Arnoldi algorithm is developed for accelerating PageRank computations. The new method is called Arnoldi-PET algorithm, whose implementation and convergence are analyzed. Numerical experiments on several examples are used to illustrate the effectiveness of our proposed algorithm.
MSC:
65F15 Numerical computation of eigenvalues and eigenvectors of matrices
Software:
eigs; IRAM; SNAP; TRLan
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Page, L.; Brin, S.; Motwami, R.; Winograd, T., The PageRank Citation Ranking: Bringing Order to the WebTechnical report (1999), Computer Science Department, Stanford University: Computer Science Department, Stanford University Stanford, CA
[2] Langville, A.; Meyer, C., A survey of eigenvector methods for web information retrieval, SIAM Rev., 47, 135-161 (2005) · Zbl 1075.65053
[3] Langville, A.; Meyer, C., Deeper inside PageRank, Internet Math., 1, 335-380 (2005) · Zbl 1098.68010
[4] Berkhin, P., A survey on PageRank computing, Internet Math., 2, 73-120 (2005) · Zbl 1100.68504
[5] Berman, A.; Plemmons, R., Nonnegative Matrices in the Mathematical Sciences (1979), Academic Press: Academic Press New York · Zbl 0484.15016
[6] Meyer, C., Matrix Analysis and Applied Linear Algebra (2000), SIAM: SIAM Philadelphia, PA
[7] Langville, A.; Meyer, C., A reordering for the PageRank problem, SIAM J. Sci. Comput., 27, 2112-2120 (2006) · Zbl 1103.65048
[8] Philippe, B.; Saad, Y.; Stewart, W. J., Numerical methods in Markov chain modeling, Oper. Res., 40, 1156-1179 (1992) · Zbl 0764.65095
[9] Golub, G. H.; Van Loan, C. F., Matrix Computations (1996), The Johns Hopkins University Press: The Johns Hopkins University Press Baltimore, London · Zbl 0865.65009
[10] Haveliwala, T. H.; Kamvar, S. D.; Klein, D.; Manning, C.; Golub, G. H., Computing PageRank using Power Extrapolation (2003), Stanford University Technical Report
[11] Kamvar, S.; Haveliwala, T.; Manning, C.; Golub, G., Extrapolation methods for accelerating PageRank computations, (Proceedings of the Twelfth Internatinal World Wide Web Conference (2003), ACM Press: ACM Press New York), 261-270
[12] Pu, B. Y.; Huang, T. Z.; Wen, C., A preconditioned and extrapolation-accelerated GMRES method for PageRank, Appl. Math. Lett., 37, 95-100 (2014) · Zbl 1314.65057
[13] Tan, X. Y., A new extrapolation method for pagerank computations, J. Comput. Appl. Math., 313, 383-392 (2017) · Zbl 1353.65028
[14] Brezinski, C.; Redivo-Zaglia, M., The PageRank vector: properties, computation, approximation, and acceleration, SIAM J. Matrix Anal. Appl., 28, 551-575 (2006) · Zbl 1116.65042
[15] 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) · Zbl 1145.65312
[16] Gleich, D.; Gray, A.; Greif, C.; Lau, T., An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32, 349-371 (2010) · Zbl 1209.65043
[17] Wen, C.; Huang, T. Z.; Shen, Z. L., A note on the two-step matrix splitting iteration for computing pagerank, J. Comput. Appl. Math., 315, 87-97 (2017) · Zbl 1354.65068
[18] Gu, C. Q.; Wang, L., On the multi-splitting iteration method for computing pagerank, J. Appl. Math. Comput., 42, 479-490 (2013) · Zbl 1295.65039
[19] Gu, C. Q.; Xie, F.; Zhang, K., A two-step matrix splitting iteration for computing pagerank, J. Comput. Appl. Math., 278, 19-28 (2015) · Zbl 1304.65132
[20] Gu, C. Q.; Jiang, X. L.; Nie, Y.; Chen, Z. B., A preprocessed multi-step splitting iteration for computing PageRank, Appl. Math. Comput., 338, 87-100 (2018) · Zbl 1427.65046
[21] Bai, Z. Z., On convergence of the inner-outer iteration method for computing pagerank, Numer. Algebra Control Optim., 2, 855-862 (2012) · Zbl 1264.65041
[22] Tian, Z. L.; Liu, Y.; Zhang, Y.; Liu, Z. Y.; Tian, M. Y., The general inner-outer iteration method based on regular splittings for the PageRank problem, Appl. Math. Comput., 356, 479-501 (2019) · Zbl 1429.65079
[23] Kamvar, S. D.; Haveliwala, T. H.; Golub, G. H., Adaptive methods for the computation of PageRank, Linear Algebra Appl., 386, 51-65 (2004) · Zbl 1091.68044
[24] Yin, J. F.; Yin, G. J.; Ng, M., On adaptively accelerated Arnoldi method for computing PageRank, Numer. Linear Algebra Appl., 19, 73-85 (2012) · Zbl 1274.65109
[25] Langville, A.; Meyer, C., Updating PageRank with iterative aggregation, (Proceedings of the Thirteenth World Wide Web Conference (2004), ACM Press: ACM Press New York), 392-393
[26] Lin, Y. Q.; Shi, X. H.; Wei, Y. M., On computing PageRank via lumping the Google matrix, J. Comput. Appl. Math., 224, 702-708 (2009) · Zbl 1167.68367
[27] Yu, Q.; Miao, Z.k.; Wu, G.; Wei, Y. M., Lumping algorithms for computing Googles PageRank and its derivative, with attention to unreferenced nodes, Inf. Retr., 15, 503-526 (2012)
[28] Golub, G. H.; Greif, C., An Arnoldi-type algorithm for computing PageRank, BIT, 46, 759-771 (2006) · Zbl 1105.65034
[29] Wu, G.; Wei, Y., A Power-Arnoldi algorithm for computing pagerank, Numer. Linear Algebra Appl., 14, 521-546 (2007) · Zbl 1199.65125
[30] Wu, G.; Wei, Y., An Arnoldi-Extrapolation algorithm for computing PageRank, J. Comput. Appl. Math., 234, 3196-3212 (2010) · Zbl 1201.65059
[31] Morgan, R.; Zeng, M., A harmonic restarted Arnoldi algorithm for calculating eigenvalues and determining multiplicity, Linear Algebra Appl., 415, 96-113 (2006) · Zbl 1088.65033
[32] Gu, C. Q.; Wang, W. W., An Arnoldi-Inout algorithm for computing PageRank problems, J. Comput. Appl. Math., 309, 219-229 (2017) · Zbl 06626244
[33] Gu, C. Q.; Jiang, X. L.; Shao, C. C.; Chen, Z. B., A GMRES-Power algorithm for computing PageRank problems, J. Comput. Appl. Math., 343, 113-123 (2018) · Zbl 06892258
[34] Shen, Z. L.; Huang, T. Z.; Carpentieri, B.; Gu, X. M.; Wen, C., An efficient elimination strategy for solving pagerank problems, Appl. Math. Comput., 298, 111-122 (2017) · Zbl 1411.65053
[35] Zhang, H. F.; Huang, T. Z.; Wen, C.; Shen, Z. L., FOM accelerated by an extrapolation method for solving pagerank problems, J. Comput. Appl. Math., 296, 397-409 (2016) · Zbl 1336.65058
[36] Horn, R.; Johnson, C., Matrix Analysis (1985), Cambridge Universtiy Press · Zbl 0576.15001
[37] Arnoldi, W. E., The principle of minimized iteration in the solution of the matrix eigenvalue problem, Q. Appl. Math., 9, 17-29 (1951) · Zbl 0042.12801
[38] Wu, K.; Simon, H., Thick-restart Lanczos method for large symmetric eigenvalue problems, SIAM J. Matrix Anal. Appl., 22, 602-616 (2000) · Zbl 0969.65030
[39] Sorensen, D., Implicit application of polynomial filters in a k-step Arnoldi method, SIAM J. Matrix Anal. Appl., 13, 357-385 (1992) · Zbl 0763.65025
[40] Langville, A.; Meyer, C., Google’s PageRank and beyond: The Science of the Search Engine Rankings (2006), Princeton University Press · Zbl 1104.68042
[41] Haveliwala, T.; Kamvar, S., The Second Eigenvalue of the Google MatrixTechnical report (2003), Stanford University: Stanford University Stanford, CA
[42] Saad, Y., Numerical Methods for Large Eigenvalue Problems (1992), Manchester University Press · Zbl 0991.65039
[43] https://sparse.tamu.edu/Gleich/wb-cs-stanford.
[44] https://sparse.tamu.edu/SNAP/web-Stanford.
[45] https://sparse.tamu.edu/Kamvar/Stanford-Berkeley.
[46] https://sparse.tamu.edu/SNAP/web-Google.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.