Skip to Main content Skip to Navigation

Could any graph be turned into a small-world?

Abstract : 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.
Document type :
Complete list of metadata
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:49 AM
Last modification on : Wednesday, December 1, 2021 - 2:37:04 PM


Files produced by the author(s)


  • HAL Id : hal-02101877, version 1



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⟩



Les métriques sont temporairement indisponibles