Random walks on small world networks
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 {𝑢, 𝑣 } with distance 𝑑 > 1 is added as a “long-range" edge with probability proportional to 𝑑−𝑟, where 𝑟 ≥ 0 is a parameter of the model...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Association for Computing Machinery
2020
|
| _version_ | 1826262763437031424 |
|---|---|
| author | Dyer, ME Galanis, A Goldberg, L Jerrum, M Vigoda, E |
| author_facet | Dyer, ME Galanis, A Goldberg, L Jerrum, M Vigoda, E |
| author_sort | Dyer, ME |
| collection | OXFORD |
| description | 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 {𝑢, 𝑣 } with distance 𝑑 > 1 is added as a “long-range" edge with probability proportional to 𝑑−𝑟, where 𝑟 ≥ 0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is 𝑂( (log𝑛)2) when 𝑟 = 2 and 𝑛Ω(1) when 𝑟 ≠ 2. Here, we prove that the random walk also undergoes a phase transition at 𝑟 = 2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(log𝑛) for 𝑟 < 2, 𝑂( (log𝑛)4) for 𝑟 = 2 and 𝑛 Ω(1) for 𝑟 > 2. |
| first_indexed | 2024-03-06T19:41:13Z |
| format | Journal article |
| id | oxford-uuid:20b89e0c-63a0-46eb-bc3d-9b97ab00b0de |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T19:41:13Z |
| publishDate | 2020 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:20b89e0c-63a0-46eb-bc3d-9b97ab00b0de2022-03-26T11:29:15ZRandom walks on small world networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:20b89e0c-63a0-46eb-bc3d-9b97ab00b0deEnglishSymplectic ElementsAssociation for Computing Machinery2020Dyer, MEGalanis, AGoldberg, LJerrum, MVigoda, EWe 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 {𝑢, 𝑣 } with distance 𝑑 > 1 is added as a “long-range" edge with probability proportional to 𝑑−𝑟, where 𝑟 ≥ 0 is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is 𝑂( (log𝑛)2) when 𝑟 = 2 and 𝑛Ω(1) when 𝑟 ≠ 2. Here, we prove that the random walk also undergoes a phase transition at 𝑟 = 2, but in this case the phase transition is of a different form. We establish that the mixing time is Θ(log𝑛) for 𝑟 < 2, 𝑂( (log𝑛)4) for 𝑟 = 2 and 𝑛 Ω(1) for 𝑟 > 2. |
| spellingShingle | Dyer, ME Galanis, A Goldberg, L Jerrum, M Vigoda, E Random walks on small world networks |
| title | Random walks on small world networks |
| title_full | Random walks on small world networks |
| title_fullStr | Random walks on small world networks |
| title_full_unstemmed | Random walks on small world networks |
| title_short | Random walks on small world networks |
| title_sort | random walks on small world networks |
| work_keys_str_mv | AT dyerme randomwalksonsmallworldnetworks AT galanisa randomwalksonsmallworldnetworks AT goldbergl randomwalksonsmallworldnetworks AT jerrumm randomwalksonsmallworldnetworks AT vigodae randomwalksonsmallworldnetworks |