Hostname: page-component-7b7567c8c-7pwfn Total loading time: 0 Render date: 2026-11-16T23:50:48.144Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  04 January 2016

Louigi Addario-Berry*
Affiliation:
McGill University
Tao Lei*
Affiliation:
McGill University
*
∗ Postal address: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street West, Montréal, Québec, H3A 0B9, Canada.
∗ Postal address: Department of Mathematics and Statistics, McGill University, 805 Sherbrooke Street West, Montréal, Québec, H3A 0B9, Canada.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

‘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 model, the mixing time is of order log2 n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2 n and an upper bound of order log3 n.

Information

Type
General Applied Probability
Copyright
© Applied Probability Trust