Small worlds

DOI10.1002/RSA.1018MaRDI QIDQ2748426zbMATH OpenOpenAlexFDO

Authors A. D. Barbour, Gesine Reinert

Publication date 10 July 2002

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0006001

zbMATH Keywords

circle modelsnetworksPoisson approximationPoisson processStein's method

Mathematics Subject Classification ID

Special processes (60K99)

Abstract: Small world models are networks consisting of many local links and fewer long range `shortcuts'. In this paper, we consider some particular instances, and rigorously investigate the distribution of their inter--point network distances. Our results are framed in terms of approximations, whose accuracy increases with the size of the network. We also give some insight into how the reduction in typical inter--point distances occasioned by the presence of shortcuts is related to the dimension of the underlying space.

Review text

Consider a circle \(C\) of circumference 1 and a Poisson process of intensity \(n\) on \(C\). From each of its points a random chord is drawn to a uniformly distributed point. These chords we call ``shortcuts and let them all have ``length 0. A ``small worlds network is created with local links and long range shortcuts. Let \(D\) be the distance between two random points on \(C\) using arcs and shortcuts. One result proved in this nice paper is the convergence of \(nD - (1/4)\log n\) to a certain non-degenerate distribution as \(n\) tends to infinity; the same result holds if the number of chords is \(n\) (non-random). Also higher-dimensional results are derived. Models of this type have recently received considerable attention and have been investigated by physicists in heuristic ways, giving in some cases non-correct results, contrary to the rigorous and interesting methods of the present paper.

Recommendations

• Discrete small world networks
• Asymptotic Behaviour of Gossip Processes and Small-World Networks
• On the connectivity and diameter of small-world networks
• Efficient routeing in Poisson small-world networks
• Analyzing Kleinberg's (and other) small-world models

Cites work

• Collective dynamics of `small-world' networks
• Epidemics with two levels of mixing

Cited in

(21)

• Unravelling small world networks
• A general model for stochastic SIR epidemics with two levels of mixing
• Poisson approximations for epidemics with two levels of mixing.
• The clustering coefficient and the diameter of small-world networks
• Eclecticism shrinks even small worlds
• Discrete small world networks
• Two phase transitions for the contact process on small worlds
• An analysis of the transition zone between the various scaling regimes in the small-world model
• Greedy pathlengths and small world graphs
• Matrix analysis of a Markov chain small-world model
• The great circle epidemic model.
• First passage percolation on the Newman-Watts small world model
• Approximating dependent rare events
• Centrality analysis for modified lattices
• Asymptotic Behaviour of Gossip Processes and Small-World Networks
• On the connectivity and diameter of small-world networks
• The small world effect on the coalescing time of random walks
• Efficient routeing in Poisson small-world networks
• A Small Fib
• Asymptotic behavior of Aldous' gossip process
• Phase transitions in dynamical random graphs

This page was built for publication: Small worlds

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