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.
Origine : Fichiers produits par l'(les) auteur(s)