{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:35:06Z","timestamp":1787337306463,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Sci. Comput."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>A multilevel adaptive aggregation method for calculating the stationary probability vector of an irreducible stochastic matrix is described. The method is a special case of the adaptive smoothed aggregation and adaptive algebraic multigrid methods for sparse linear systems and is also closely related to certain extensively studied iterative aggregation\/disaggregation methods for Markov chains. In contrast to most existing approaches, our aggregation process does not employ any explicit advance knowledge of the topology of the Markov chain. Instead, adaptive agglomeration is proposed that is based on the strength of connection in a scaled problem matrix, in which the columns of the original problem matrix at each recursive fine level are scaled with the current probability vector iterate at that level. The strength of connection is determined as in the algebraic multigrid method, and the aggregation process is fully adaptive, with optimized aggregates chosen in each step of the iteration and at all recursive levels. The multilevel method is applied to a set of stochastic matrices that provide models for web page ranking. Numerical tests serve to illustrate for which types of stochastic matrices the multilevel adaptive method may provide significant speedup compared to standard iterative methods. The tests also provide more insight into why Google's PageRank model is a successful model for determining a ranking of web pages.<\/jats:p>","DOI":"10.1137\/070685142","type":"journal-article","created":{"date-parts":[[2008,6,11]],"date-time":"2008-06-11T18:02:42Z","timestamp":1213207362000},"page":"2235-2262","source":"Crossref","is-referenced-by-count":45,"title":["Multilevel Adaptive Aggregation for Markov Chains, with Application to Web Ranking"],"prefix":"10.1137","volume":"30","author":[{"given":"H.","family":"De Sterck","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thomas A.","family":"Manteuffel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stephen F.","family":"McCormick","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Quoc","family":"Nguyen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Ruge","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,6,11]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/050626272"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1137\/040614402"},{"key":"R3","unstructured":"A. Brandt, S. F. McCormick, and J. W. Ruge,\n                      Algebraic multigrid (AMG) for sparse matrix equations\n                      , in Sparsity and Its Applications, D. J. Evans, ed., Cambridge University Press, Cambridge, 1984."},{"key":"R4","unstructured":"J. Ruge,\n                      Algebraic multigrid (AMG) for geodetic survey problems\n                      , in Proceedings of the International Multigrid Conference, Copper Mountain, CO, Elsevier, New York, 1983."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.2307\/1909285"},{"key":"R6","unstructured":"Y. Takahashi,\n                      A Lumping Method for Numerical Calculations of Stationary Distributions of Markov Chains\n                      , Research Report B-18, Department of Information Sciences, Tokyo Institute of Technology, 1975."},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1137\/0605019"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/3828.214137"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90003-2"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1109\/49.62851"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"W. J. Stewart,\n                      An Introduction to the Numerical Solution of Markov Chains\n                      , Princeton University Press, Princeton, 1994.","DOI":"10.1515\/9780691223384"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(95)00166-O"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1099-1506(199807\/08)5:4<253::AID-NLA124>3.0.CO;2-B"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598338159"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/S0024-3795(02)00333-6"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1137\/040619028"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Y. Zhu, S. Ye, and X. Li,\n                      Distributed PageRank computation based on iterative aggregation-disaggregation methods\n                      , in Proceedings of the 14th ACM International Conference on Information and Knowledge Management, 2005, pp. 578\u2013585.","DOI":"10.1145\/1099554.1099705"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"G. Horton and S. T. Leutenegger,\n                      A Multi-Level Solution Algorithm for Steady-State Markov Chains\n                      , ACM SIGMETRICS, New York, 1994, pp. 191\u2013200.","DOI":"10.1145\/183018.183040"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"S. T. Leutenegger and G. Horton,\n                      On the utility of the multi-level algorithm for the solution of nearly completely decomposable Markov chains\n                      , in Numerical Solution of Markov Chains, W. Stewart, ed., Kluwer, Norwell, MA, 1995, pp. 425\u2013443.","DOI":"10.1007\/978-1-4615-2241-6_24"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"U. R. Krieger,\n                      Numerical solution of large finite Markov chains by algebraic multigrid techniques\n                      , in Numerical Solution of Markov Chains, W. Stewart, ed., Kluwer, Norwell, MA, 1995, pp. 403\u2013424.","DOI":"10.1007\/978-1-4615-2241-6_23"},{"key":"R21","unstructured":"C. Isensee and G. Horton,\n                      A Multi-Level Method for the Steady State Solution of Markov Chains\n                      , Simulation und Visualisierung, SCS European Publishing House, Bonn, 2004."},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1137\/040615729"},{"key":"R23","unstructured":"L. Page, S. Brin, R. Motwani, and T. Winograd,\n                      The PageRank Citation Ranking: Bringing Order to the Web\n                      , Technical report 1999-0120, Computer Science Department, Stanford, 1999."},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503424786"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2004.10129091"},{"key":"R27","unstructured":"T. H. Haveliwala and S. D. Kamvar,\n                      The Second Eigenvalue of the Google Matrix\n                      , Technical report 2003-0020, Computer Science Department, Stanford, 2003."},{"key":"R28","unstructured":"Stanford Web Matrix, http:\/\/nlp.stanford.edu\/~sdkamvar\/data\/stanford-web.tar.gz."},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1016\/0096-3003(86)90095-0"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1137\/S1064827598339402"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. Ruge and K. Stueben,\n                      Algebraic multigrid\n                      , in Multigrid Methods, S. F. McCormick, ed., Frontiers Appl. Math. 3, SIAM, Philadelphia, 1987, pp. 73\u2013130.","DOI":"10.1137\/1.9781611971057.ch4"}],"container-title":["SIAM Journal on Scientific Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/070685142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:56:04Z","timestamp":1787334964000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/070685142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/070685142"],"URL":"https:\/\/doi.org\/10.1137\/070685142","relation":{},"ISSN":["1064-8275","1095-7197"],"issn-type":[{"value":"1064-8275","type":"print"},{"value":"1095-7197","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}