Random walks on small world networks

DOI10.1145/3382208zbMATH Open1484.05195arXiv1707.02467OpenAlexW3033587075MaRDI QIDQ4987458FDOQ4987458

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)

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$.

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

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

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)

Cited In (11)

• Neighbor selection and hitting probability in small-world graphs
• The mixing time of the Newman-Watts small world
• Random spreading phenomena in annealed small world networks
• Scale-free percolation mixing time
• The small world effect on the coalescing time of random walks
• 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
• Title not available (Why is that?)
• Speeding up random walk mixing by starting from a uniform vertex

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)