Could any graph be turned into a small world ?
Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel · HAL (Le Centre pour la Communication Scientifique Directe) · 2004
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.