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

DOI10.1239/aap/1427814580zbMath1309.60002arXiv1201.3795OpenAlexW1982313773MaRDI QIDQ5246170

Tao Lei, Louigi Addario-Berry

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

zbMATH Keywords

mixing timerandom graphsmall worldconductance bound

Mathematics Subject Classification ID

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

Related Items (5)

First passage percolation on the Newman-Watts small world model ⋮ Smoothed Analysis on Connected Graphs ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Improved mixing rates of directed cycles by added connection ⋮ Isoperimetric numbers of randomly perturbed intersection graphs

Uses Software

• MathOverflow

Cites Work

• Faster mixing and small bottlenecks
• Renormalization group analysis of the small-world network model
• The Diameter of a Cycle Plus a Random Matching
• Maximum hitting time for random walks on graphs
• The Structure and Function of Complex Networks
• The Diameter of Sparse Random Graphs
• Collective dynamics of ‘small-world’ networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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