Shifted power-GMRES method accelerated by extrapolation for solving PageRank with multiple damping factors. (English) Zbl 1510.65070
Summary: Starting from the seminal paper published by S. Brin and L. Page [“The anatomy of a large-scale hypertextual web search engine”, Comput. Networks ISDN Syst. 30, No. 1, 107-117 (1998; doi:10.1016/S0169-7552(98)00110-X)], the PageRank model has been extended to many fields far beyond search engine rankings, such as chemistry, biology, bioinformatics, social network analysis, to name a few. Due to the large dimension of PageRank problems, in the past decade or so, considerable research efforts have been devoted to their efficient solution especially for the difficult cases where the damping factors are close to 1. However, there exists few research work concerning about the solution of the case where several PageRank problems with the same network structure and various damping factors need to be solved. In this paper, we generalize the Power method to solving the PageRank problem with multiple damping factors. We demonstrate that the solution has almost the equative cost of solving the most difficult PageRank system of the sequence, and the residual vectors of the PageRank systems after running this method are collinear. Based upon these results, we develop a more efficient method that combines this Power method with the shifted GMRES method. For further accelerating the solving phase, we present a seed system choosing strategy combined with an extrapolation technique, and analyze their effect. Numerical experiments demonstrate the potential of the proposed iterative solver for accelerating realistic PageRank computations with multiple damping factors.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
PageRank; shifted linear systems; multiple damping factors; Krylov subspace methods; extrapolation; power methodReferences:
| [1] | S. Brin, L. Page, The anatomy of a large-scale hypertextual web search engine, 1998. |
| [2] | Liu, B.; Jiang, S.; Zou, Q., HITS-PR-HHblits: protein remote homology detection by combining PageRank and hyperlink-induced topic search, Brief. Bioinf., 21, 1, 298-308 (2020) |
| [3] | Massucci, F. A.; Docampo, D., Measuring the academic reputation through citation networks via pagerank, J. Inf., 13, 1, 185-201 (2019) |
| [4] | Page, L.; Brin, S.; Motwani, R.; Winograd, T., The PageRank Citation Ranking: Bringing Order to the Web, Technical report (1999), Stanford InfoLab |
| [5] | Rafiei, M.; Kardan, A. A., A novel method for expert finding in online communities based on concept map and PageRank, Hum.-Centric Comput. Inf. Sci., 5, 1, 10 (2015) |
| [6] | Zhang, M.; Li, X.; Zhang, L.; Khurshid, S., Boosting spectrum-based fault localization using PageRank, Proceedings of the 26th ACM SIGSOFT International Symposium on Software Testing and Analysis, 261-272 (2017) |
| [7] | Zhou, T.; Martinez-Baez, E.; Schenter, G.; Clark, A. E., PageRank as a collective variable to study complex chemical transformations and their energy landscapes, J. Chem. Phys., 150, 13, 134102 (2019) |
| [8] | Gleich, D. F., Pagerank beyond the web, SIAM Rev., 57, 321-363 (2015) · Zbl 1336.05122 |
| [9] | Constantine, P. G.; Gleich, D. F., Random alpha PageRank, Internet Math., 6, 189-236 (2009) · Zbl 1210.68135 |
| [10] | Kamvar, S. D.; Haveliwala, T. H.; Manning, C. D.; Golub, G. H., Extrapolation methods for accelerating PageRank computation, Proc. of the 12th International World Wide Web Conference, 261-270 (2003) |
| [11] | Tan, X., A new extrapolation method for PageRank computations, J. Comput. Appl. Math., 313, 383-392 (2017) · Zbl 1353.65028 |
| [12] | Kamvar, S. D.; Haveliwala, T. H.; Golub, G. H., Adaptive methods for the computation of the PageRank, Linear Algebra Appl., 386, 51-65 (2004) · Zbl 1091.68044 |
| [13] | Sterck, H. D.; Manteuffel, T. A.; McCormick, S. F.; Nguyen, Q.; Ruge, J., Multilevel adaptive aggregation for Markov chains, with application to web ranking, SIAM J. Sci. Comput., 30, 2235-2262 (2008) · Zbl 1173.65028 |
| [14] | Shen, Z.-L.; Huang, T.-Z.; Carpentieri, B.; Wen, C.; Gu, X. M., Block-accelerated aggregation multigrid for Markov chains with application to PageRank problems, Commun. Nonlinear. Sci., 59, 472-487 (2018) · Zbl 1510.94105 |
| [15] | Gleich, D. F.; Gray, A. P.; Greif, C.; Lau, T., An inner-outer iteration for computing PageRank, SIAM J. Sci. Comput., 32, 349-371 (2010) · Zbl 1209.65043 |
| [16] | 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 |
| [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] | 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 |
| [19] | Tian, M.-Y.; Zhang, Y.; Wang, Y. D., A general multi-splitting iteration method for computing PageRank, Comput. Appl. Math., 38, 1-29 (2019) · Zbl 1438.65068 |
| [20] | Golub, G. H.; Greif, C., An Arnoldi-type algorithm for computing PageRank, BIT, 46, 759-771 (2006) · Zbl 1105.65034 |
| [21] | 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 |
| [22] | 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 |
| [23] | Wu, G.; We, Y. M., Arnoldi versus GMRES for computing PageRank: a theoretical contribution to google’s PageRank problem, ACM Trans. Inf. Syst., 28, 1-28 (2010) |
| [24] | 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 |
| [25] | Gleich, D. F.; Zhukov, L.; Berkhin, P., Fast Parallel PageRank: A Linear System Approach, Yahoo! 489 Tech. Rep. (2005) |
| [26] | Wu, G.; Wei, Y., A power-Arnoldi algorithm for computing PageRank, Numer. Linear Algebra Appl., 14, 521-546 (2007) · Zbl 1199.65125 |
| [27] | 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 1524.65167 |
| [28] | Hu, Q.-Y.; Wen, C.; Huang, T.-Z.; Shen, Z.-L.; Gu, X. M., A variant of the power-Arnoldi algorithm for computing PageRank, J. Comput. Appl. Math., 381, 113034 (2021) · Zbl 1452.65068 |
| [29] | Gu, C.-Q.; Wang, W. W., An Arnoldi-inout algorithm for computing PageRank problems, J. Comput. Appl. Math., 309, 219-229 (2017) · Zbl 1468.65033 |
| [30] | Langville, A. N.; Meyer, C. D., Deeper inside PageRank, Internet Math., 1, 335-380 (2004) · Zbl 1098.68010 |
| [31] | Haveliwala, T.; Kamvar, S., The Second Eigenvalue of the Google Matrix, Stanford University Technical Report (2003) |
| [32] | Corso, G. M.D.; Gulli, A.; Romani, F., Fast PageRank computation via a sparse linear system, Internet Math., 2, 251-273 (2005) · Zbl 1095.68578 |
| [33] | Young, D. M., Iterative Solution of Large Linear Systems (1971), Academic Press: Academic Press New York · Zbl 0231.65034 |
| [34] | Greif, C.; Kurokawa, D., A note on the convergence of SOR for the PageRank problem, SIAM J. Sci. Comput., 33, 3201-3209 (2011) · Zbl 1232.65054 |
| [35] | Xie, Y.-J.; Ma, C. F., A relaxed two-step splitting iteration method for computing PageRank, Comput. Appl. Math., 37, 221-233 (2018) · Zbl 1397.65053 |
| [36] | Corso, G. M.D.; Gulli, A.; Romani, F., Comparison of Krylov subspace methods on the PageRank problem, J. Comput. Appl. Math., 210, 159-166 (2007) · Zbl 1134.65026 |
| [37] | Wu, G.; Wei, Y., An Arnoldi-extrapolation algorithm for computing PageRank, J. Comput. Appl. Math., 234, 3196-3212 (2010) · Zbl 1201.65059 |
| [38] | Kamvar, S. D.; Haveliwala, T. H.; Manning, C. D.; Goloub, G. H., Exploiting the Block Structure of the Web for Computing PageRank, Technical Report (2003), Stanford University |
| [39] | Yu, Q.; Miao, Z.; Wu, G.; Wei, Y. M., Lumping algorithms for computing google’s PageRank and its derivative, with attention to unreferenced nodes, Inf. Retr., 15, 503-526 (2012) |
| [40] | 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 |
| [41] | Shen, Z.-L.; Huang, T.-Z.; Carpentieri, B.; Wen, C.; Gu, X.-M.; Tan, X. Y., Off-diagonal low-rank preconditioner for difficult PageRank problems, J. Comput. Appl. Math., 346, 456-470 (2019) · Zbl 1402.65028 |
| [42] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), SIAM: SIAM Philadelphia · Zbl 1002.65042 |
| [43] | Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018 |
| [44] | Frommer, A.; Glassner, U., Restarted GMRES for shifted linear systems, SIAM J. Sci. Comput., 19, 15-26 (1998) · Zbl 0912.65023 |
| [45] | van der Vorst, H. A., Bi-CGSTAB: a fast and smoothly converging variant of Bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 631-644 (1992) · Zbl 0761.65023 |
| [46] | Walker, F. H.; Ni, P., Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 49, 1715-1735 (2011) · Zbl 1254.65067 |
| [47] | Available at the URL: http://www.cise.ufl.edu/research/sparse/matrices · Zbl 1365.65123 |
| [48] | Boldi, P.; Vigna, S., The WebGraph framework I: compression techniques, Proc. of the 13th international conference on World Wide Web, 595-602 (2004) |
| [49] | Boldi, P.; Rosa, M.; Santini, M.; Vigna, S., Layered label propagation: a multiresolution coordinate-free ordering for compressing social networks, Proc. of the 20th International Conference on World Wide Web, 587-596 (2011) |
| [50] | Boldi, P.; Codenotti, B.; Santini, M.; Vigna, S., UbiCrawler: a scalable fully distributed web crawler, Softw. Pract. Experience, 34, 711-726 (2004) |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
