Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-30T23:19:49.475Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Behaviour of Gossip Processes and Small-World Networks

Part of: Markov processes Special processes

Published online by Cambridge University Press:  04 January 2016

A. D. Barbour  and
G. Reinert
A. D. Barbour*
Affiliation:
Universität Zürich and National University of Singapore
G. Reinert*
Affiliation:
University of Oxford
*
∗ Postal address: Angewandte Mathematik, Universität Zürich, Winterthurertrasse 190, CH-8057 Zürich, Switzerland.
∗∗ Postal address: Department of Statistics, University of Oxford, 1 South Parks Road, Oxford OX1 3TG, UK.
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.

Both small-world models of random networks with occasional long-range connections and gossip processes with occasional long-range transmission of information have similar characteristic behaviour. The long-range elements appreciably reduce the effective distances, measured in space or in time, between pairs of typical points. In this paper we show that their common behaviour can be interpreted as a product of the locally branching nature of the models. In particular, it is shown that both typical distances between points and the proportion of space that can be reached within a given distance or time can be approximated by formulae involving the limit random variable of the branching process.

Keywords

Small-world graphgossip processbranching process approximation

MSC classification

Secondary: 60K35: Interacting random processes; statistical mechanics type models; percolation theory 60J85: Applications of branching processes
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 45 , Issue 4 , December 2013 , pp. 981 - 1010
Copyright
© Applied Probability Trust 

Footnotes

ADB was Saw Swee Hock Professor at the National University of Singapore while part of this work was carried out. Work supported in part by the Australian Research Council grants DP120102728 and DP120102398.

Supported in part by the EPSRC and BBSRC through OCISB.

References

Aldous, D. J. (2013). When knowing early matters: gossip, percolation and Nash equilibria. In Prokhorov and Contemporary Probability Theory (Springer Proc. Math. Statist. 33), eds Shiryaev, A. N., Varadhan, S. R. S. and Presman, E. L., Springer, Berlin, pp. 3–27.Google Scholar
Ball, F., Mollison, D. and Scalia-Tomba, G. (1997). Epidemics with two levels of mixing. Ann. Appl. Prob. 7, 46–89.Google Scholar
Ball, F., Sirl, D. and Trapman, P. (2013). Epidemics on random intersection graphs. To appear in Ann. Appl. Prob. Google Scholar
Barbour, A. D. and Reinert, G. (2001). Small worlds. Random Structures Algorithms 19, 54–74. (Correction: 25 (2004), 115.)Google Scholar
Bhamidi, S., van der Hofstad, R. and Hooghiemstra, G. (2012). Universality for first passage percolation on sparse random graphs. Preprint. Available at http://arxiv.org/abs/1210.6839v1.Google Scholar
Chatterjee, S. and Durrett, R. (2011). Asymptotic behavior of Aldous' gossip process. Ann. Appl. Prob. 21, 2447–2482.CrossRefGoogle Scholar
McDiarmid, C. (1998). Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (Algorithms Combinatorics 16), eds Habib, M. et al., Springer, Berlin, pp. 195–248.CrossRefGoogle Scholar
Moore, C. and Newman, M. E. J. (2000). Epidemics and percolation in small-world networks. Phys. Rev. E 61, 5678–5682.Google Scholar
Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small–world’ networks. Nature 393, 440–442.Google Scholar