Asymptotic behaviour of gossip processes and small-world networks.

*(English)*Zbl 1308.60107In [“Collective dynamics of ‘small-world’ networks”, Nature 393, 440–442 (1998; doi:10.1038/30918)], D. J. Watts and S. H. Strogatz have provided a “small-world” model, where a random number of chords are superimposed as shortcuts on a circle \(C\) of circumference \(L\). The chords have endpoints uniformly and independently distributed on \(C\), and the number of chords follows a Poisson distribution.

Further, C. Moore and M. E. J. Newman [“Epidemics and percolation in small-world networks”, Phys. Rev. E 61, 5678–5682 (2000; doi:10.1103/PhysRevE.61.5678)] generalized the Watts and Strogatz’ model to a continuous analogue. A closely related model, the so-called “great circle model”, was earlier introduced by F. Ball et al. [Ann. Appl. Probab. 7, No. 1, 46–89 (1997; Zbl 0909.92028)].

In the present paper, the authors consider the Poisson process above on a smooth, closed, homogeneous Riemannian manifold \(C\) of dimension \(d\), such as a sphere or a torus, having large finite volume \(|C|=L\) with respect to its intrinsic metric.

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 authors show that their common behaviour can be interpreted as a product of the locally branching nature of the models.

Further, C. Moore and M. E. J. Newman [“Epidemics and percolation in small-world networks”, Phys. Rev. E 61, 5678–5682 (2000; doi:10.1103/PhysRevE.61.5678)] generalized the Watts and Strogatz’ model to a continuous analogue. A closely related model, the so-called “great circle model”, was earlier introduced by F. Ball et al. [Ann. Appl. Probab. 7, No. 1, 46–89 (1997; Zbl 0909.92028)].

In the present paper, the authors consider the Poisson process above on a smooth, closed, homogeneous Riemannian manifold \(C\) of dimension \(d\), such as a sphere or a torus, having large finite volume \(|C|=L\) with respect to its intrinsic metric.

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 authors show that their common behaviour can be interpreted as a product of the locally branching nature of the models.

Reviewer: Sophia L. Kalpazidou (Thessaloniki)

##### MSC:

60K35 | Interacting random processes; statistical mechanics type models; percolation theory |

60J85 | Applications of branching processes |

05C82 | Small world graphs, complex networks (graph-theoretic aspects) |

PDF
BibTeX
XML
Cite

\textit{A. D. Barbour} and \textit{G. Reinert}, Adv. Appl. Probab. 45, No. 4, 981--1010 (2013; Zbl 1308.60107)

**OpenURL**

##### References:

[1] | 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 A. N. Shiryaev, S. R. S. Varadhan and E. L. Presman, Springer, Berlin, pp. 3-27. · Zbl 1270.60112 |

[2] | Ball, F., Mollison, D. and Scalia-Tomba, G. (1997). Epidemics with two levels of mixing. Ann. Appl. Prob. 7 , 46-89. · Zbl 0909.92028 |

[3] | Ball, F., Sirl, D. and Trapman, P. (2013). Epidemics on random intersection graphs. To appear in Ann. Appl. Prob. · Zbl 1291.92098 |

[4] | Barbour, A. D. and Reinert, G. (2001). Small worlds. Random Structures Algorithms 19 , 54-74. (Correction: 25 (2004), 115.) · Zbl 0988.60100 |

[5] | 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. · Zbl 1213.60157 |

[6] | Chatterjee, S. and Durrett, R. (2011). Asymptotic behavior of Aldous’ gossip process. Ann. Appl. Prob. 21 , 2447-2482. · Zbl 1246.60117 |

[7] | McDiarmid, C. (1998). Concentration. In Probabilistic Methods for Algorithmic Discrete Mathematics (Algorithms Combinatorics 16 ), eds M. Habib et al. , Springer, Berlin, pp. 195-248. · Zbl 0927.60027 |

[8] | Moore, C. and Newman, M. E. J. (2000). Epidemics and percolation in small-world networks. Phys. Rev. E 61 , 5678-5682. |

[9] | Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature 393 , 440-442. · Zbl 1368.05139 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.