{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T06:47:53Z","timestamp":1787381273071,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Matrix Anal. Appl."],"published-print":{"date-parts":[[2003,1]]},"abstract":"<jats:p>We use techniques from applied matrix analysis to study small world cutoff in a Markov chain. Our model consists of a periodic random walk plus uniform jumps. This has a direct interpretation as a teleporting random walk, of the type used by search engines to locate web pages, on a simple ring network. More loosely, the model may be regarded as an analogue of the original small world network of Watts and Strogatz [Nature, 393 (1998), pp. 440-442]. We measure the small world property by expressing the mean hitting time, averaged over all states, in terms of the expected number of shortcuts per random walk. This average mean hitting time is equivalent to the expected number of steps between a pair of states chosen uniformly at random. The analysis involves nonstandard matrix perturbation theory and the results come with rigorous and sharp asymptotic error estimates. Although developed in a different context, the resulting cutoff diagram agrees closely with that arising from the mean-field network theory of Newman, Moore, and Watts [Phys. Rev. Lett., 84 (2000), pp. 3201-3204].<\/jats:p>","DOI":"10.1137\/s0895479802406142","type":"journal-article","created":{"date-parts":[[2003,9,19]],"date-time":"2003-09-19T21:40:15Z","timestamp":1064007615000},"page":"429-444","source":"Crossref","is-referenced-by-count":9,"title":["A Matrix Perturbation View of the Small World Phenomenon"],"prefix":"10.1137","volume":"25","author":[{"given":"Desmond J.","family":"Higham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,31]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.1018"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-90157-6"},{"key":"R3","volume-title":"Random walks in biology","author":"Berg Howard","year":"1983"},{"key":"R4","unstructured":"H. Caswell,\n                      Matrix Population Models\n                      , 2nd ed., Sinauer Associates, Sunderland, MA, 2001."},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971446"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1142\/S0219525901000140"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.66.066702"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.2165\/00129785-200303010-00001"},{"key":"R9","volume-title":"Accuracy and stability of numerical algorithms","author":"Higham Nicholas","year":"1996"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"S. D. Kamvar, T. H. Haveliwala, C. D. Manning, and G. H. Golub,\n                      Extrapolation methods for accelerating pagerank computations\n                      , in Proceedings of the Twelfth International World Wide Web Conference, Budapest, Hungary, 2003.","DOI":"10.1145\/775152.775190"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Karlin and H. M. Taylor,\n                      A First Course in Stochastic Processes\n                      , 2nd ed., Academic Press, San Diego, 1975.","DOI":"10.1016\/B978-0-08-057041-9.50005-2"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480102409048"},{"key":"R14","unstructured":"C. Moler,\n                      The world\u2019s largest matrix computation\n                      , MATLAB News and Notes, October 2002."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1006\/jtbi.2001.2460"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.021544898"},{"key":"R18","doi-asserted-by":"publisher","unstructured":"M. Newman, The structure and function of networks, Proceedings of the Europhysics Conference on Computational Physics (CCP 2001) (Aachen), Vol. 147, 2002, 40\u20134510.1016\/S0010-4655(02)00201-11913364","DOI":"10.1016\/S0010-4655(02)00201-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.84.3201"},{"key":"R20","volume-title":"Markov chains","author":"Norris J.","year":"1998"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971323"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1038\/35065725"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1098\/rspb.2001.1711"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"D. J. Watts,\n                      Small Worlds: The Dynamics of Networks between Order and Randomness\n                      , Princeton University Press, Princeton, NJ, 1999.","DOI":"10.1515\/9780691188331"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1038\/30918"}],"container-title":["SIAM Journal on Matrix Analysis and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895479802406142","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T17:38:02Z","timestamp":1787333882000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895479802406142"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,1]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2003,1]]}},"alternative-id":["10.1137\/S0895479802406142"],"URL":"https:\/\/doi.org\/10.1137\/s0895479802406142","relation":{},"ISSN":["0895-4798","1095-7162"],"issn-type":[{"value":"0895-4798","type":"print"},{"value":"1095-7162","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,1]]}}}