Could any graph be turned into a small-world?

In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163–170] showed that a small-world can also be seen as a graph in which the routing t...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2006-01, Vol.355 (1), p.96-103
Main Authors: Duchon, Philippe, Hanusse, Nicolas, Lebhar, Emmanuelle, Schabanel, Nicolas
Format: Article
Language:English
Subjects:
Computer Science
Other
Random graph model
Routing algorithm
Small-world
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In addition to statistical graph properties (diameter, degree, clustering, etc.), Kleinberg [The small-world phenomenon: an algorithmic perspective, in: Proc. 32nd ACM Symp. on Theory of Computing (STOC), 2000, pp. 163–170] showed that a small-world can also be seen as a graph in which the routing task can be efficiently and easily done in spite of a lack of global knowledge. 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2005.12.008