On the average path length of deterministic and stochastics recursive networks

Philippe Giabbanelli 1 Dorian Mazauric 1, 2 Jean-Claude Bermond 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
2 MAESTRO - Models for the performance analysis and the control of networks
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : The average shortest path distance between all pairs of nodes in real-world networks tends to be small compared to the number of nodes. Providing a closed-form formula for remains challenging in several network models, as shown by recent papers dedicated to this sole topic. For example, Zhang et al. proposed the deterministic model ZRG and studied an upper bound on . In this paper, we use graph-theoretic techniques to establish a closed-form formula for in ZRG. Our proof is of particular interests for other network models relying on similar recursive structures, as found in fractal models. We extend our approach to a stochastic version of ZRG in which layers of triangles are added with probability p. We find a first-order phase transition at the critical probability pc = 0.5, from which the expected number of nodes becomes infinite whereas expected distances remain finite. We show that if triangles are added independently instead of being constrained in a layer, the first-order phase transition holds for the very same critical probability. Thus, we provide an insight showing that models can be equivalent, regardless of whether edges are added with grouping constraints. Our detailed computations also provide thorough practical cases for readers unfamiliar with graph-theoretic and probabilistic techniques.
Type de document :
Communication dans un congrès
CompletNet, 2010, Rio de Janeiro, Brazil. 2010
Liste complète des métadonnées

Contributeur : Dorian Mazauric <>
Soumis le : jeudi 4 novembre 2010 - 16:28:12
Dernière modification le : lundi 5 octobre 2015 - 16:56:53
Document(s) archivé(s) le : samedi 5 février 2011 - 03:05:10


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00532890, version 1



Philippe Giabbanelli, Dorian Mazauric, Jean-Claude Bermond. On the average path length of deterministic and stochastics recursive networks. CompletNet, 2010, Rio de Janeiro, Brazil. 2010. <inria-00532890>



Consultations de
la notice


Téléchargements du document