Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-22T17:07:26.105Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Part of: Combinatorial probability Graph theory

Published online by Cambridge University Press:  04 January 2016

Louigi Addario-Berry  and
Tao Lei
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 log2n. This confirms a prediction of Richard Durrett [5, page 22], who proved a lower bound of order log2n and an upper bound of order log3n.

Keywords

Random graphsmall worldmixing timeconductance bound

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05C81: Random walks on graphs 05C82: Small world graphs, complex networks
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 47 , Issue 1 , March 2015 , pp. 37 - 56
Copyright
© Applied Probability Trust 

References

Angel, O. (2011). Answer to: Counting subtrees of a random tree (random Catalan numbers). Available at http://mathoverflow.net/questions/66595.Google Scholar
Bollobás, B. and Chung, F. R. K. (1988). The diameter of a cycle plus a random matching. SIAM J. Discrete Math. 1, 328–333.Google Scholar
Brightwell, G. and Winkler, P. (1990). Maximum hitting time for random walks on graphs. Random Structures Algorithms 1, 263–276.Google Scholar
Condamin, S. et al. (2007). First-passage times in complex scale-invariant media. Nature 450, 77–80.Google Scholar
Durrett, R. (2007). Random Graph Dynamics. Cambridge University Press.Google Scholar
Farkas, I. J., Derényi, I., Barabási, A. L. and Vicsek, T. (2001). Spectra of ‘real-world’ graphs: beyond the semicircle law. Phys. Rev. E 64, 026704.Google Scholar
Fountoulakis, N. and Reed, B. A. (2007). Faster mixing and small bottlenecks. Prob. Theory Relat. Fields 137, 475–486.CrossRefGoogle Scholar
Gallos, L. K., Song, C., Havlin, S. and Makse, H. A. (2007). Scaling theory of transport in complex biological networks. Proc. Nat. Acad. Sci. USA 104, 7746–7751.Google Scholar
Janson, S., Łuczak, T. and Ruciński, A. (2000). Random Graphs. John Wiley, New York.Google Scholar
Jasch, F. and Blumen, A. (2001). Target problem on small-world networks. Phys. Rev. E 63, 041108.Google Scholar
Jespersen, S., Sokolov, I. M. and Blumen, A. (2000). Relaxation properties of small-world networks. Phys. Rev. E 62, 4405.Google Scholar
Levin, D. A., Peres, Y. and Wilmer, E. L. (2009). Markov Chains and Mixing Times. American Mathematical Society, Providence, RI.Google Scholar
Lovász, L. and Winkler, P. (1998). Mixing times. In Microsurveys in Discrete Probability (Princeton, NJ, 1997; DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 41), American Mathematical Society, Providence, RI, pp. 85–133.Google Scholar
Monasson, R. (1999). Diffusion, localization and dispersion relations on ‘small-world’ lattices. Europ. Phys. J. B 12, 555–567.Google Scholar
Montenegro, R. and Tetali, P. (2006). Mathematical aspects of mixing times in Markov chains. Found. Trends Theoret. Comput. Sci. 1, 121pp.Google Scholar
Newman, M. E. J. (2003). The structure and function of complex networks. SIAM Rev. 45, 167–256.Google Scholar
Newman, M. E. J. and Watts, D. J. (1999). Renormalization group analysis of the small-world network model. Phys. Lett. A 263, 341–346.Google Scholar
Newman, M. E. J. and Watts, D. J. (1999). Scaling and percolation in the small-world network model. Phys. Rev. E 60, 7332.Google Scholar
Newman, M. E. J., Barabási, A.-L. and Watts, D. J. (eds) (2006). The Structure and Dynamics of Networks. Princeton University Press.Google Scholar
Noh, J. D. and Rieger, H. (2004). Random walks on complex networks. Phys. Rev. Lett. 92, 118701.Google Scholar
Riordan, O. and Wormald, N. (2010). The diameter of sparse random graphs. Combin. Prob. Comput. 19, 835–926.CrossRefGoogle Scholar
Stanley, R. P. (1999). Enumerative Combinatorics, Vol 2. Cambridge University Press.Google Scholar
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature 393, 440–442.Google Scholar