Understanding and modeling the small-world phenomenon in dynamic networks

Anh-Dung Nguyen (1) , Patrick Sénac (1) , Michel Diaz (1)

1 LAAS-SARA - Équipe Services et Architectures pour Réseaux Avancés

The small-world phenomenon first introduced in the context of static graphs consists of graphs with high clustering coefficient and low shortest path length. This is an intrinsic property of many real complex static networks. Recent research has shown that this structure is also observable in dynamic networks but how it emerges remains an open problem. In this paper, we propose a model capable of capturing the small-world behavior observed in various real traces. We then study information diffusion in such small-world networks. Analytical and simulation results with epidemic model show that the small-world structure increases dramatically the information spreading speed in dynamic networks.

Mots clés: DTN; Temporal graph; Network structure; Small-world phenomenon; Information diffusion

Domaines: Réseaux et télécommunications [cs.NI]

Anh-Dung Nguyen, Patrick Sénac, Michel Diaz. Understanding and modeling the small-world phenomenon in dynamic networks. The 15th ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWIM 2012), Oct 2012, Paphos, Cyprus. pp.377-384. ⟨hal-00908491⟩