{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:46Z","timestamp":1787337226282,"version":"build-2736575974"},"reference-count":46,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>We present a new iterative scheme for PageRank computation. The algorithm is applied to the linear system formulation of the problem, using inner-outer stationary iterations. It is simple, can be easily implemented and parallelized, and requires minimal storage overhead. Our convergence analysis shows that the algorithm is effective for a crude inner tolerance and is not sensitive to the choice of the parameters involved. The same idea can be used as a preconditioning technique for nonstationary schemes. Numerical examples featuring matrices of dimensions exceeding 100,000,000 in sequential and parallel environments demonstrate the merits of our technique. Our code is available online for viewing and testing, along with several large scale examples.<\/jats:p>","DOI":"10.1137\/080727397","type":"journal-article","created":{"date-parts":[[2010,2,5]],"date-time":"2010-02-05T18:13:52Z","timestamp":1265393632000},"page":"349-371","source":"Crossref","is-referenced-by-count":75,"title":["An Inner-Outer Iteration for Computing PageRank"],"prefix":"10.1137","volume":"32","author":[{"given":"David F.","family":"Gleich","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew P.","family":"Gray","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chen","family":"Greif","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tracy","family":"Lau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,2,5]]},"reference":[{"key":"R1","unstructured":"A. Arasu, J. Novak, A. Tomkins, and J. Tomlin,\n                      PageRank Computation and the Structure of the Web: Experiments and Algorithms\n                      , in Proceedings of the 11th International Conference on the World Wide Web, Honolulu, 2002, available online from http:\/\/www2002.org\/CDROM\/poster\/173.pdf."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"K. Avrachenkov, N. Litvak, and K. S. Pham,\n                      Distribution of PageRank mass among principle components of the web\n                      , in Proceedings of the 5th Workshop on Algorithms and Models for the Web Graph, A. Bonato and F. C. Graham, eds., Lecture Notes in Comput. Sci. 4863, Springer-Verlag, 2007, pp. 16\u201328.","DOI":"10.1007\/978-3-540-77004-6_2"},{"key":"R3","unstructured":"M. Bayati, M. Gerritsen, D. F. Gleich, A. Saberi, and Y. Wang,\n                      Matching Wikipedia categories to the Library of Congress subject headings with network alignment\n                      , submitted."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129098"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"A. Berman and R. Plemmons,\n                      Nonnegative Matrices in the Mathematical Sciences\n                      , revised reprint of the 1979 original, Classics Appl. Math. 9, SIAM, Philadelphia, 1994.","DOI":"10.1137\/1.9781611971262"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1145\/1052934.1052938"},{"key":"R7","unstructured":"P. Boldi, R. Posenato, M. Santini, and S. Vigna,\n                      Traps and Pitfalls of Topic-BiasedPageRank\n                      , in Algorithms and Models for the Web-Graph, Lecture Notes in Comput. Sci., Springer-Verlag, Berlin, Heidelberg, 2007."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"P. Boldi, M. Santini, and S. Vigna,\n                      PageRank as a function of the damping factor\n                      , in Proceedings of the 14th International Conference on the World Wide Web, Chiba, Japan, 2005, pp. 557\u2013566.","DOI":"10.1145\/1060745.1060827"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"P. Boldi and S. Vigna,\n                      The webgraph framework\n                      I:\n                      Compression techniques\n                      , in Proceedings of the 13th International Conference on the World Wide Web, New York, 2004, pp. 595\u2013602.","DOI":"10.1145\/988672.988752"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-52-01910-8"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2005.01.015"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1137\/050623280"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2006.10.080"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"N. Eiron, K. S. McCurley, and J. A. Tomlin,\n                      Ranking the web frontier\n                      , in Proceedings of the 13th International Conference on the World Wide Web, New York, 2004, pp. 309\u2013318.","DOI":"10.1145\/988672.988714"},{"key":"R15","unstructured":"L. Eld\u00e9n,\n                      A Note on the Eigenvalues of the Google Matrix\n                      , Report LiTH-MAT-R-04-01, Link\u00f6ping University, Link\u00f6ping, Sweden, 2003."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/0731085"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142995293742"},{"key":"R18","unstructured":"D. Gleich, L. Zhukov, and P. Berkhin,\n                      Fast Parallel PageRank: A Linear System Approach\n                      , Yahoo! Research Technical Report YRL-2004-038, available online from http:\/\/research.yahoo.com\/publication\/YRL-2004-038.pdf, 2004."},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1007\/s10543-006-0091-y"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01397553"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"G. Grimmett and D. Stirzaker,\n                      Probability and Random Processes\n                      , 3rd ed., Oxford University Press, Oxford, UK, 2001.","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"key":"R22","doi-asserted-by":"crossref","unstructured":"Z. Gy\u00f6ngyi, H. Garcia-Molina, and J. Pedersen,\n                      Combating Web spam with TrustRank\n                      , in Proceedings of the 30th International Conference on Very Large Data Bases, Toronto, 2004, pp. 576\u2013587.","DOI":"10.1016\/B978-012088469-8.50052-8"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"W. Hackbusch,\n                      Iterative Solution of Large Sparse Systems of Equations\n                      , Springer-Verlag, New York, 1994.","DOI":"10.1007\/978-1-4612-4288-8"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1137\/060664331"},{"key":"R25","unstructured":"S. Kamvar and T. Haveliwala,\n                      The Condition Number of the PageRank Problem\n                      , Technical report, Stanford University, Stanford, CA, 2003, available online from http:\/\/dbpubs.stanford.edu:8090\/pub\/2003-36."},{"key":"R26","doi-asserted-by":"crossref","unstructured":"S. Kamvar, T. Haveliwala, C. Manning, and G. Golub,\n                      Extrapolation methods for accelerating PageRank computations\n                      , in Proceedings of the 12th International Conference on the World Wide Web, Budapest, 2003, pp. 261\u2013270.","DOI":"10.1145\/775152.775190"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"C. Karande, K. Chellapilla, and R. Andersen,\n                      Speeding up algorithms on compressed web graphs\n                      , in Proceedings of the 2nd ACM International Conference on Web Search and Data Mining, Barcelona, 2009, pp. 272\u2013281.","DOI":"10.1145\/1498759.1498836"},{"key":"R28","unstructured":"G. Kollias, E. Gallopoulos, and D. Szyld,\n                      Asynchronous iterative computations with Web information retrieval structures: The PageRank case\n                      , in Parallel Computing: Current and Future Issues of High-End Computing, NIC Ser. 33, John von Neumann Institut f\u00fcr Computing, J\u00fclich, Germany, 2006, pp. 309\u2013316."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503424786"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"A. Langville and C. Meyer,\n                      Google's PageRank and Beyond: The Science of Search Engine Rankings\n                      , Princeton University Press, Princeton, NJ, 2006.","DOI":"10.1515\/9781400830329"},{"key":"R31","unstructured":"C. Lee, G. Golub, and S. Zenios,\n                      A Fast Two-Stage Algorithm for Computing PageRank and Its Extensions\n                      , Technical report SCCM-03-15, Stanford University, Stanford, CA, 2003."},{"key":"R32","doi-asserted-by":"crossref","unstructured":"F. McSherry,\n                      A uniform approach to accelerated PageRank computation\n                      , in Proceedings of the 14th International Conference on the World Wide Web, Chiba, Japan, 2005, pp. 575\u2013582.","DOI":"10.1145\/1060745.1060829"},{"key":"R33","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-6-233"},{"key":"R34","doi-asserted-by":"crossref","unstructured":"M. A. Najork, H. Zaragoza, and M. J. Taylor,\n                      Hits on the web: How does it compare?\n                      , in Proceedings of the 30th International ACM SIGIR Conference on Research and Development in Information Retrieval, New York, 2007, pp. 471\u2013478.","DOI":"10.1145\/1277741.1277823"},{"key":"R35","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd,\n                      The PageRank Citation Ranking: Bringing Order to the Web\n                      , Stanford Digital Libraries, 1999, available online from http:\/\/dbpubs.stanford.edu:8090\/pub\/1999-66."},{"key":"R36","unstructured":"J. Parreira, D. Donato, S. Michel, and G. Weikum,\n                      Efficient and decentralized PageRank approximation in a peer-to-peer web search network\n                      , in Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, 2006, pp. 415\u2013426."},{"key":"R37","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479804441407"},{"key":"R38","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827502406415"},{"key":"R39","doi-asserted-by":"crossref","unstructured":"R. Singh, J. Xu, and B. Berger,\n                      Pairwise global alignment of protein interaction networks by matching neighborhood topology\n                      , in Research in Computational Molecular Biology, Lecture Notes in Comput. Sci. 4453, Springer-Verlag, Berlin, Heidelberg, pp. 16\u201331.","DOI":"10.1007\/978-3-540-71681-5_2"},{"key":"R40","unstructured":"W. Stewart,\n                      Introduction to the Numerical Solution of Markov Chains\n                      , Princeton University Press, Princeton, NJ, 1994."},{"key":"R41","unstructured":"The Library of Congress Subject Headings\n                      , http:\/\/id.loc.gov\/authorities\/search\/. Accessed via http:\/\/lcsh.info, September 2008."},{"key":"R42","unstructured":"R. Varga,\n                      Matrix Iterative Analysis\n                      , Prentice\u2013Hall, Englewood Cliffs, NJ, 1962."},{"key":"R43","unstructured":"S. Vigna, R. Posenato, and M. Santini,\n                      Law $1.3.1$ - Library of Algorithms for the Webgraph\n                      , http:\/\/law.dsi.unimi.it\/software\/docs\/."},{"key":"R44","unstructured":"Wikipedia XML Database Dump from April 2, $2007$.\n                      Accessed from http:\/\/en.wikipedia.org\/ wiki\/Wikipedia:Database_download, April 2007."},{"key":"R45","doi-asserted-by":"publisher","DOI":"10.1137\/070698129"},{"key":"R46","doi-asserted-by":"crossref","unstructured":"D. Zhou, J. Huang, and Sch\u00f6lkopf,\n                      Learning from labeled and unlabeled data on a directed graph\n                      , in Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 2005, pp. 1036\u20131043.","DOI":"10.1145\/1102351.1102482"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080727397","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:50:39Z","timestamp":1787334639000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080727397"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":46,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080727397"],"URL":"https:\/\/doi.org\/10.1137\/080727397","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}