Random walks on small world networks

DOI10.1145/3382208MaRDI QIDQ4987458zbMATH OpenOpenAlexFDO

Authors Martin Dyer, Andreas Galanis, Leslie Ann Goldberg, Eric Vigoda, Mark Jerrum

Publication date 3 May 2021

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.02467

zbMATH Keywords

random walkphase transitionmixing timeconductancesmall world

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Random walks on graphs (05C81)

Abstract: 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>1$ is added as a "long-range" edge with probability proportional to $d^{-r}$, where $rgeq0$ is a parameter of the model. Kleinberg studied a close variant of this network model and proved that the (decentralised) routing time is $O((logn{)}^2)$ when $r=2$ and $n^{Omega(1)}$ when $req2$. Here, we prove that the random walk also undergoes a phase transition at $r=2$, but in this case the phase transition is of a different form. We establish that the mixing time is $Theta(logn)$ for $r<2$, $O((logn{)}^4)$ for $r=2$ and $n^{Omega(1)}$ for $r>2$.

Recommendations

• The Mixing Time of the Newman-Watts Small-World Model
• The mixing time of the Newman-Watts small world
• Mixing Time of Random Walk on Poisson Geometry Small World
• On the modified Newman-Watts small world and its random walk
• The small world effect on the coalescing time of random walks

Cited in

(11)

• Neighbor selection and hitting probability in small-world graphs
• Speeding up random walk mixing by starting from a uniform vertex
• The mixing time of the Newman-Watts small world
• Random spreading phenomena in annealed small world networks
• The small world effect on the coalescing time of random walks
• Scale-free percolation mixing time
• A Matrix Perturbation View of the Small World Phenomenon
• Scaling properties of a random walk on small-world networks with an open boundary
• Spatio-spectral limiting on discrete tori: adjacency invariant spaces
• On the modified Newman-Watts small world and its random walk
• scientific article; zbMATH DE number 1950482 (Why is no real title available?)

This page was built for publication: Random walks on small world networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987458)