{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T11:52:07Z","timestamp":1759665127441,"version":"3.41.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T00:00:00Z","timestamp":1591401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}]},{"name":"EPSRC research","award":["EP\/M004953\/1, EP\/N004221\/1 and EP\/I011935\/1"],"award-info":[{"award-number":["EP\/M004953\/1, EP\/N004221\/1 and EP\/I011935\/1"]}]},{"name":"ERC","award":["334828"],"award-info":[{"award-number":["334828"]}]},{"name":"NSF","award":["CCF-1617306 and CCF-1563838"],"award-info":[{"award-number":["CCF-1617306 and CCF-1563838"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,7,31]]},"abstract":"<jats:p>\n            We study the mixing time of random walks on small-world networks modelled as follows: starting with the 2-dimensional periodic grid, each pair of vertices {u,v} with distance d&gt; 1 is added as a \u201clong-range\u201d edge with probability proportional to d\n            <jats:sup>-r<\/jats:sup>\n            , where r\u2265 0 is a parameter of the model. Kleinberg [33{ studied a close variant of this network model and proved that the (decentralised) routing time is O((log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>2<\/jats:sup>\n            ) when\n            <jats:italic>r<\/jats:italic>\n            =2 and n\n            <jats:sup>\u03a9 (1)<\/jats:sup>\n            when r\u2260 2. Here, we prove that the random walk also undergoes a phase transition at\n            <jats:italic>r=2<\/jats:italic>\n            , but in this case, the phase transition is of a different form. We establish that the mixing time is \u03f4 (log n) for r&lt; 2, O((log\n            <jats:italic>n<\/jats:italic>\n            )\n            <jats:sup>4<\/jats:sup>\n            ) for\n            <jats:italic>r<\/jats:italic>\n            =2, and\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\u03a9 (1)<\/jats:sup>\n            for r&gt; 2.\n          <\/jats:p>","DOI":"10.1145\/3382208","type":"journal-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T00:47:00Z","timestamp":1591490820000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Random Walks on Small World Networks"],"prefix":"10.1145","volume":"16","author":[{"given":"Martin E.","family":"Dyer","sequence":"first","affiliation":[{"name":"University of Leeds, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Galanis","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leslie Ann","family":"Goldberg","sequence":"additional","affiliation":[{"name":"University of Oxford, Oxford, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mark","family":"Jerrum","sequence":"additional","affiliation":[{"name":"Queen Mary, University of London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Vigoda","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/130949191"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1239\/aap\/1427814580"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01219071"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01205489"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"I. Benjamini and N. Berger. 2001. The diameter of long-range percolation clusters on finite cycles. Random Structures 8 Algorithms 19 2 (2001) 102--111.  I. Benjamini and N. Berger. 2001. The diameter of long-range percolation clusters on finite cycles. Random Structures 8 Algorithms 19 2 (2001) 102--111.","DOI":"10.1002\/rsa.1022"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308008948"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"I. Benjamini H. Kesten Y. Peres and O. Schramm. 2004. Geometry of the uniform spanning forest: Transitions in dimensions 4 8 12 \u2026 Annals of Mathematics 160 2 (2004) 465--491.  I. Benjamini H. Kesten Y. Peres and O. Schramm. 2004. Geometry of the uniform spanning forest: Transitions in dimensions 4 8 12 \u2026 Annals of Mathematics 160 2 (2004) 465--491.","DOI":"10.4007\/annals.2004.160.465"},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"I. Benjamini G. Kozma and N. Wormald. 2014. The mixing time of the giant component of a random graph. Random Structures 8 Algorithms 45 3 (2014) 383--407.  I. Benjamini G. Kozma and N. Wormald. 2014. The mixing time of the giant component of a random graph. Random Structures 8 Algorithms 45 3 (2014) 383--407.","DOI":"10.1002\/rsa.20539"},{"key":"e_1_2_1_9_1","unstructured":"N. Berger. 2004. A lower bound for the chemical distance in sparse long-range percolation models. arXiv:math\/0409021.  N. Berger. 2004. A lower bound for the chemical distance in sparse long-range percolation models. arXiv:math\/0409021."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1214\/009117904000000577"},{"volume-title":"Graph diameter in long-range percolation. Random Structures 8 Algorithms 39, 2","year":"2011","author":"Biskup M.","key":"e_1_2_1_11_1"},{"key":"e_1_2_1_12_1","unstructured":"M. Biskup and J. Lin. 2017. Sharp asymptotic for the chemical distance in long-range percolation. arXiv:1705.10380.  M. Biskup and J. Lin. 2017. Sharp asymptotic for the chemical distance in long-range percolation. arXiv:1705.10380."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403004"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-017-0796-7"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"C. Bordenave P. Caputo and J. Salez. 2018. Cutoff at the \u201centropic time\u201d for sparse Markov chains. Probability Theory and Related Fields.  C. Bordenave P. Caputo and J. Salez. 2018. Cutoff at the \u201centropic time\u201d for sparse Markov chains. Probability Theory and Related Fields.","DOI":"10.1007\/s00440-018-0834-0"},{"volume-title":"Proceedings of the 24th IEEE International Conference on Computer Communications (INFOCOM), 1653--1664","author":"Boyd S.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","unstructured":"T. K. Carne. 1985. A transmutation formula for Markov chains. Bull. Sci. Math. 109 (1985) 399--405.  T. K. Carne. 1985. A transmutation formula for Markov chains. Bull. Sci. Math. 109 (1985) 399--405."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.11.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"D. Coppersmith D. Gamarnik and M. Sviridenko. 2002. The diameter of a long-range percolation graph. Random Structures 8 Algorithms 21 1 (2002) 1--13.  D. Coppersmith D. Gamarnik and M. Sviridenko. 2002. The diameter of a long-range percolation graph. Random Structures 8 Algorithms 21 1 (2002) 1--13.","DOI":"10.1002\/rsa.10042"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-011-0383-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1214\/11-AOP647"},{"key":"e_1_2_1_22_1","unstructured":"J. Ding and A. Sly. 2013. Distances in critical long range percolation. arXiv:1303.3995.  J. Ding and A. Sly. 2013. Distances in critical long range percolation. arXiv:1303.3995."},{"volume-title":"Random Graph Dynamics","author":"Durrett R.","key":"e_1_2_1_23_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546594"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2007.10129290"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"A. D. Flaxman and A. M. Frieze. 2007. The diameter of randomly perturbed digraphs and some applications. Random Structures 8 Algorithms 30 4 (2007) 484--504.  A. D. Flaxman and A. M. Frieze. 2007. The diameter of randomly perturbed digraphs and some applications. Random Structures 8 Algorithms 30 4 (2007) 484--504.","DOI":"10.1002\/rsa.20172"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01651330"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-006-0003-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"N. Fountoulakis and B. A. Reed. 2008. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Structures 8 Algorithms 33 1 (2008) 68--86.  N. Fountoulakis and B. A. Reed. 2008. The evolution of the mixing rate of a simple random walk on the giant component of a random graph. Random Structures 8 Algorithms 33 1 (2008) 68--86.","DOI":"10.1002\/rsa.20210"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"A. Frieze and M. Karo\u0144ski. 2015. Introduction to Random Graphs. Cambridge University Press.  A. Frieze and M. Karo\u0144ski. 2015. Introduction to Random Graphs. Cambridge University Press.","DOI":"10.1017\/CBO9781316339831"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100034241"},{"key":"e_1_2_1_31_1","unstructured":"S. Janson R. Kozma M. Ruszink\u00f3 and Y. Sokolov. 2015. Bootstrap percolation on a random graph coupled with a lattice. arXiv:1507.07997.  S. Janson R. Kozma M. Ruszink\u00f3 and Y. Sokolov. 2015. Bootstrap percolation on a random graph coupled with a lattice. arXiv:1507.07997."},{"volume-title":"Proceedings of the 44th IEEE Symposium on Foundations of Computer Science (FOCS), 482--491","author":"Kempe D.","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335325"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Congress of Mathematicians (ICM)","volume":"3","author":"Kleinberg J.","year":"2006"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/151002496"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"D. A. Levin and Y. Peres. 2017. Markov Chains and Mixing Times 2nd edition. American Mathematical Society.  D. A. Levin and Y. Peres. 2017. Markov Chains and Mixing Times 2nd edition. American Mathematical Society.","DOI":"10.1090\/mbk\/107"},{"volume-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC), 282--287","author":"Lov\u00e1sz L.","key":"e_1_2_1_37_1"},{"key":"e_1_2_1_38_1","doi-asserted-by":"crossref","unstructured":"R.\n      Lyons\n     and \n      Y.\n      Peres\n  . \n  2016\n  . Probability on Trees and Networks volume \n  42\n   of \n  Cambridge Series in Statistical and Probabilistic Mathematics\n  . \n  Cambridge University Press New York.  R. Lyons and Y. Peres. 2016. Probability on Trees and Networks volume 42 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press New York.","DOI":"10.1017\/9781316672815"},{"volume-title":"Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), 179--188","author":"Martel C.","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","unstructured":"S. Milgram. 1967. The small world problem. Psychology Today 2 (1967) 60--67.  S. Milgram. 1967. The small world problem. Psychology Today 2 (1967) 60--67."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/2786545"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP358"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01211064"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(99)00757-4"},{"volume-title":"Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 311--320","author":"Nguyen V.","key":"e_1_2_1_45_1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/16\/17\/001"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_48_1","first-page":"225","article-title":"Long range estimates for Markov chains","volume":"109","author":"Varopoulos N. T.","year":"1985","journal-title":"Bull. Sci. Math."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382208","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3382208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:02:09Z","timestamp":1750197729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3382208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,6]]},"references-count":48,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,7,31]]}},"alternative-id":["10.1145\/3382208"],"URL":"https:\/\/doi.org\/10.1145\/3382208","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,6,6]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}