Could any graph be turned into a small-world? - LARA - Libre accès aux rapports scientifiques et techniques
Rapport (Rapport De Recherche) Année : 2004

Could any graph be turned into a small-world?

Résumé

In addition to statistical graph properties (diameter, degree, clustering, ...), Kleinberg showed in 2000 that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done. More precisely, in a lattice network augmented by extra random edges (but not chosen uniformly), a short path of polylogarithmic expected length can be found using a greedy algorithm with a local knowledge of the nodes. We call such a graph a navigable small-world since short paths exist and can be followed with partial knowledge of the network. In this paper, we show that a wide class of graphs can be augmented into navigable small-worlds.
Outre des propriété statistiques de graphes (diamètre, degré, connectivité,...) Kleinberg a montré qu'un petit monde peut aussi être considéré comme un graphe où le routage se fait aisément, et de façon efficace. Plus précisément, dans une grille de dimension 2 augmentée par des longs liens aléatoires supplémentaires (mais qui ne sont pas choisis uniformément), l'algorithme glouton trivial trouve un chemin court de longueur moyenne polylogarithmique en utilisant uniquement une connaissance locale des nœuds. nous appelons un tel graphe petiti monde navigable, puisque des chemins courts existent et peuvent être suivis en utilisant une connaissance partielle du réseau. Dans cet article, nous montrons qu'il existe une classe important e de graphes pouvant être augmentés en petits mondes navigables.
Fichier principal
Vignette du fichier
RR2004-61.pdf (247 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-02101877 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101877 , version 1

Citer

Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel. Could any graph be turned into a small-world?. [Research Report] LIP RR-2004-61, Laboratoire de l'informatique du parallélisme. 2004, 2+7p. ⟨hal-02101877⟩
28 Consultations
161 Téléchargements

Partager

More