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
* Auteur correspondant
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 : 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.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru et Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. pp.TBA, 2010
Liste complète des métadonnées

https://hal.inria.fr/inria-00472215
Contributeur : Giabbanelli Philippe <>
Soumis le : samedi 10 avril 2010 - 21:13:30
Dernière modification le : dimanche 11 avril 2010 - 16:59:19
Document(s) archivé(s) le : mardi 14 septembre 2010 - 17:54:38

Fichier

algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00472215, version 1

Collections

Citation

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

Partager

Métriques

Consultations de
la notice

265

Téléchargements du document

526