HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Saturday, April 10, 2010 - 9:13:30 PM
Last modification on : Thursday, January 20, 2022 - 5:32:19 PM
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