The Mixing Time of the Newman-Watts Small-World Model

DOI10.1239/AAP/1427814580MaRDI QIDQ5246170zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Tao Lei

Publication date 17 April 2015

Published in Advances in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3795, https://projecteuclid.org/euclid.aap/1427814580

zbMATH Keywords

conductance boundmixing timerandom graphsmall world

Mathematics Subject Classification ID

Random walks on graphs (05C81) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Combinatorial probability (60C05)

Abstract: "Small worlds" are large systems in which any given node has only a few connections to other points, but possessing the property that all pairs of points are connected by a short path, typically logarithmic in the number of nodes. The use of random walks for sampling a uniform element from a large state space is by now a classical technique; to prove that such a technique works for a given network, a bound on the mixing time is required. However, little detailed information is known about the behaviour of random walks on small-world networks, though many predictions can be found in the physics literature. The principal contribution of this paper is to show that for a famous small-world random graph model known as the Newman--Watts small world, the mixing time is of order (log n)^2. This confirms a prediction of Richard Durrett, who proved a lower bound of order (log n)^2 and an upper bound of order (log n)^3.

Recommendations

• The mixing time of the Newman-Watts small world
• The small world effect on the coalescing time of random walks
• Mixing time of near-critical random graphs
• Mixing Time of Random Walk on Poisson Geometry Small World
• On the modified Newman-Watts small world and its random walk
• Mixing time of exponential random graphs
• First passage percolation on the Newman-Watts small world model
• Comparing mixing times on sparse random graphs
• Comparing mixing times on sparse random graphs
• The mixing time of the giant component of a random graph

Cites work

• Collective dynamics of `small-world' networks
• Faster mixing and small bottlenecks
• scientific article; zbMATH DE number 1195779 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Maximum hitting time for random walks on graphs
• Random graph dynamics
• Renormalization group analysis of the small-world network model
• The Diameter of a Cycle Plus a Random Matching
• The diameter of sparse random graphs
• The structure and dynamics of networks
• The Structure and Function of Complex Networks

Cited in

(13)

• Random spreading phenomena in annealed small world networks
• Improved mixing rates of directed cycles by added connection
• Isoperimetric numbers of randomly perturbed intersection graphs
• Average case analysis of the Markov chain small-world model
• First passage percolation on the Newman-Watts small world model
• Mixing time of molecules inside of nanoporous gold
• Smoothed Analysis on Connected Graphs
• Mixing Time of Random Walk on Poisson Geometry Small World
• Random walks on small world networks
• On the modified Newman-Watts small world and its random walk
• The small world effect on the coalescing time of random walks
• The mixing time of the Newman-Watts small world
• Speeding up random walk mixing by starting from a uniform vertex

Describes a project that uses

Uses Software

• MathOverflow

This page was built for publication: The Mixing Time of the Newman-Watts Small-World Model

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