{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:10:46Z","timestamp":1760235046370,"version":"build-2065373602"},"reference-count":30,"publisher":"MDPI AG","issue":"8","license":[{"start":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T00:00:00Z","timestamp":1626998400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the Two-Way Support Programs of Sichuan Agricultural University","award":["1921993077"],"award-info":[{"award-number":["1921993077"]}]},{"name":"the Gruppo Nazionale per il Calcolo Scientifico (GNCS) of the Istituto Nazionale di Alta Matematica (INdAM) under Progetti di Ricerca 2020","award":["INdAM-GNCS"],"award-info":[{"award-number":["INdAM-GNCS"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Symmetry"],"abstract":"<jats:p>The PageRank model computes the stationary distribution of a Markov random walk on the linking structure of a network, and it uses the values within to represent the importance or centrality of each node. This model is first proposed by Google for ranking web pages, then it is widely applied as a centrality measure for networks arising in various fields such as in chemistry, bioinformatics, neuroscience and social networks. For example, it can measure the node centralities of the gene-gene annotation network to evaluate the relevance of each gene with a certain disease. The networks in some fields including bioinformatics are undirected, thus the corresponding adjacency matrices are symmetry. Mathematically, the PageRank model can be stated as finding the unit positive eigenvector corresponding to the largest eigenvalue of a transition matrix built upon the linking structure. With rapid development of science and technology, the networks in real applications become larger and larger, thus the PageRank model always desires numerical algorithms with reduced algorithmic or memory complexity. In this paper, we propose a novel preconditioning approach for solving the PageRank model. This approach transforms the original PageRank eigen-problem into a new one that is more amenable to solve. We then present a preconditioned version of the refined Arnoldi method for solving this model. We demonstrate theoretically that the preconditioned Arnoldi method has higher execution efficiency and parallelism than the refined Arnoldi method. In plenty of numerical experiments, this preconditioned method exhibits noticeably faster convergence speed over its standard counterpart, especially for difficult cases with large damping factors. Besides, this superiority maintains when this technique is applied to other variants of the refined Arnoldi method. Overall, the proposed technique can give the PageRank model a faster solving process, and this will possibly improve the efficiency of researches, engineering projects and services where this model is applied.<\/jats:p>","DOI":"10.3390\/sym13081327","type":"journal-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T10:31:44Z","timestamp":1627036304000},"page":"1327","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Preconditioned Variant of the Refined Arnoldi Method for Computing PageRank Eigenvectors"],"prefix":"10.3390","volume":"13","author":[{"given":"Zhao-Li","family":"Shen","sequence":"first","affiliation":[{"name":"College of Science, Sichuan Agricultural University, Ya\u2019an 625000, China"},{"name":"Johann Bernoulli Institute for Mathematics and Computer Science, Faculty of Science and Engineering, University of Groningen, 9700 AK Groningen, The Netherlands"}]},{"given":"Hao","family":"Yang","sequence":"additional","affiliation":[{"name":"College of Science, Sichuan Agricultural University, Ya\u2019an 625000, China"}]},{"given":"Bruno","family":"Carpentieri","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, Free University of Bozen-Bolzano, 39100 Bolzano, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7895-2050","authenticated-orcid":false,"given":"Xian-Ming","family":"Gu","sequence":"additional","affiliation":[{"name":"School of Economic Mathematics, Southwestern University of Finance and Economics, Chengdu 611130, China"}]},{"given":"Chun","family":"Wen","sequence":"additional","affiliation":[{"name":"School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, China"}]}],"member":"1968","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Langville, A.N., and Meyer, C.D. (2006). Google\u2019s Pagerank and Beyond: The Science of Search Engine Rankings, Princeton University Press. [3rd ed.].","DOI":"10.1515\/9781400830329"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1137\/140976649","article-title":"PageRank beyond the web","volume":"57","author":"Gleich","year":"2015","journal-title":"SIAM Rev."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1007\/s10543-006-0091-y","article-title":"An Arnoldi-type algorithm for computing pagerank","volume":"46","author":"Golub","year":"2006","journal-title":"BIT"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.laa.2003.12.008","article-title":"Adaptive methods for the computation of the PageRank","volume":"386","author":"Kamvar","year":"2004","journal-title":"Linear Algebra Appl."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Kamvar, S.D., Haveliwala, T.H., Manning, C.D., and Golub, G.H. (2003, January 20\u201324). Extrapolation methods for accelerating PageRank computation. Proceedings of the 12th International World Wide Web Conference, Budapest, Hungary.","DOI":"10.1145\/775189.775190"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"3196","DOI":"10.1016\/j.cam.2010.02.009","article-title":"An Arnoldi-Extrapolation algorithm for computing PageRank","volume":"234","author":"Wu","year":"2010","journal-title":"J. Comput. Appl. Math."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/j.cam.2016.08.034","article-title":"A new extrapolation method for PageRank computations","volume":"313","author":"Tan","year":"2017","journal-title":"J. Comput. Appl. Math."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"2235","DOI":"10.1137\/070685142","article-title":"Multilevel adaptive aggregation for Markov chains, with application to web ranking","volume":"30","author":"Sterck","year":"2008","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1016\/j.cnsns.2017.11.031","article-title":"Block-accelerated aggregation multigrid for Markov chains with application to PageRank problems","volume":"59","author":"Shen","year":"2018","journal-title":"Commun. Nonlinear Sci."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1137\/080727397","article-title":"An Inner-Outer Iteration for Computing PageRank","volume":"32","author":"Gleich","year":"2010","journal-title":"SIAM J. Sci. Comput."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/j.cam.2014.09.022","article-title":"A two-step matrix splitting iteration for computing PageRank","volume":"278","author":"Gu","year":"2015","journal-title":"J. Comput. Appl. Math."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/j.cam.2016.10.020","article-title":"A note on the two-step matrix splitting iteration for computing PageRank","volume":"315","author":"Wen","year":"2017","journal-title":"J. Comput. Appl. Math."},{"key":"ref_13","first-page":"479","article-title":"The general inner-outer iteration method based on regular splittings for the PageRank problem","volume":"356","author":"Tian","year":"2019","journal-title":"Appl. Math. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s40314-019-0830-8","article-title":"A general multi-splitting iteration method for computing PageRank","volume":"38","author":"Tian","year":"2019","journal-title":"Comput. Appl. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1002\/nla.789","article-title":"On adaptively accelerated Arnoldi method for computing PageRank","volume":"19","author":"Yin","year":"2012","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1002\/nla.531","article-title":"A power-Arnoldi algorithm for computing pagerank","volume":"14","author":"Wu","year":"2007","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"113034","DOI":"10.1016\/j.cam.2020.113034","article-title":"A variant of the Power-Arnoldi algorithm for computing PageRank","volume":"381","author":"Hu","year":"2021","journal-title":"J. Comput. Appl. Math."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.cam.2016.05.026","article-title":"An Arnoldi-Inout algorithm for computing PageRank problems","volume":"309","author":"Gu","year":"2017","journal-title":"J. Comput. Appl. Math."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Morrison, J.L., Breitling, R., Higham, D.J., and Gilbert, D.R. (2005). GeneRank: Using search engine technology for the analysis of microarray experiments. BMC Bioinform., 6.","DOI":"10.1186\/1471-2105-6-233"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1007\/s10915-013-9696-x","article-title":"Accelerating the Arnoldi-type algorithm for the PageRank problem and the ProteinRank problem","volume":"57","author":"Wu","year":"2013","journal-title":"J. Sci. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0024-3795(80)90169-X","article-title":"Variations on Arnoldi\u2019s method for computing eigenelements of large unsymmetric matrices","volume":"34","author":"Saad","year":"1980","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0024-3795(96)00238-8","article-title":"Refined iterative algorithms based on Arnoldi\u2019s process for large unsymmetric eigenproblems","volume":"259","author":"Jia","year":"1997","journal-title":"Numer. Linear Algebra Appl."},{"key":"ref_23","unstructured":"Haveliwala, T., and Kamvar, S. (2004). The Second Eigenvalue of the Google Matrix, Stanford InfoLab. Stanford University Technical Report."},{"key":"ref_24","first-page":"111","article-title":"An efficient elimination strategy for solving PageRank problems","volume":"298","author":"Shen","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"456","DOI":"10.1016\/j.cam.2018.07.015","article-title":"Off-diagonal low-rank preconditioner for difficult PageRank problems","volume":"346","author":"Shen","year":"2019","journal-title":"J. Comput. Appl. Math."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"1:1","DOI":"10.1145\/2049662.2049663","article-title":"The University of Florida sparse matrix collection","volume":"38","author":"Davis","year":"2011","journal-title":"ACM Trans. Math. Softw."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Boldi, P., and Vigna, S. (2004, January 17\u201320). The WebGraph Framework I: Compression Techniques. Proceedings of the 13th International Conference on World Wide Web, New York, NY, USA.","DOI":"10.1145\/988672.988752"},{"key":"ref_28","unstructured":"Boldi, P., Rosa, M., Santini, M., and Vigna, S. (April, January 28). Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. Proceedings of the 20th International Conference on World Wide Web, Hyderabad, India."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"711","DOI":"10.1002\/spe.587","article-title":"Ubicrawler: A scalable fully distributed Web crawler","volume":"34","author":"Boldi","year":"2004","journal-title":"Softw. Pract. Exp."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1016\/j.cam.2015.09.027","article-title":"FOM accelerated by an extrapolation method for solving PageRank problems","volume":"296","author":"Zhang","year":"2016","journal-title":"J. Comput. Appl. Math."}],"container-title":["Symmetry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/8\/1327\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T06:33:49Z","timestamp":1760164429000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2073-8994\/13\/8\/1327"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,23]]},"references-count":30,"journal-issue":{"issue":"8","published-online":{"date-parts":[[2021,8]]}},"alternative-id":["sym13081327"],"URL":"https:\/\/doi.org\/10.3390\/sym13081327","relation":{},"ISSN":["2073-8994"],"issn-type":[{"type":"electronic","value":"2073-8994"}],"subject":[],"published":{"date-parts":[[2021,7,23]]}}}