Skip to Main content Skip to Navigation
Conference papers

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 , Laboratoire I3S - 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [2 references]  Display  Hide  Download
Contributor : Dorian Mazauric Connect in order to contact the contributor
Submitted on : Thursday, November 4, 2010 - 4:28:12 PM
Last modification on : Saturday, June 25, 2022 - 11:05:03 PM
Long-term archiving on: : Saturday, February 5, 2011 - 3:05:10 AM


Files produced by the author(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. ⟨inria-00532890⟩



Record views


Files downloads