Skip to Main content Skip to Navigation
Conference papers

Computing the average path length and a label-based routing in a small-world graph

Philippe Giabbanelli 1, * Dorian Mazauric 1, 2 Stéphane Pérennes 1
* Corresponding author
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 : We study two characteristics of a small-world graph proposed by Zhang et al. to model complex networks. Our study relies on the recursive structure of the graph. Firstly, we use it to design a labelling scheme in order to create an implicit routing (i.e., a routing scheme based on the label of vertices). Secondly, proving the average distance in this graph was arduous, thus Zhang et al. chose to study the diameter: we establish a closed-form formula of the average distance, proved using the recursive structure. Thus, we characterize that the graph is small-world and not ultra small-world as was still possible. Our proof is of particular interest for other graphs based on similar recursive structures.
Document type :
Conference papers
Complete list of metadata

Cited literature [6 references]  Display  Hide  Download
Contributor : Giabbanelli Philippe <>
Submitted on : Saturday, April 10, 2010 - 9:13:30 PM
Last modification on : Tuesday, December 8, 2020 - 9:40:05 AM
Long-term archiving on: : Tuesday, September 14, 2010 - 5:54:38 PM


Files produced by the author(s)


  • HAL Id : inria-00472215, version 1



Philippe Giabbanelli, Dorian Mazauric, Stéphane Pérennes. Computing the average path length and a label-based routing in a small-world graph. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. pp.TBA. ⟨inria-00472215⟩



Record views


Files downloads