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 :
Reports
Complete list of metadatas

https://hal-lara.archives-ouvertes.fr/hal-02101877
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:49 AM
Last modification on : Friday, May 17, 2019 - 1:39:21 AM

File

RR2004-61.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101877, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

5

Files downloads

21