Could any graph be turned into a small-world?

by: Philippe Duchon, Nicolas Hanusse, Emmanuelle Lebhar, Nicolas Schabanel

Theoretical Computer Science, Vol. 355, No. 1. (6 April 2006), pp. 96-103.

View FullText article

DOI, ScienceDirect

Reviews [Write a review of this article]

There are no reviews of this article

Find related articles from these CiteULike users

ddahlem, AbnerCYH, studentx

Find related articles with these CiteULike tags

2006, algorithms, complex, evolving, graph, model, network, networks, random, small-world, stochastic

Abstract

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.

@article{citeulike:2497644, abstract = {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.}, author = {Duchon, Philippe and Hanusse, Nicolas and Lebhar, Emmanuelle and Schabanel, Nicolas }, booktitle = {Complex Networks}, citeulike-article-id = {2497644}, doi = {10.1016/j.tcs.2005.12.008}, journal = {Theoretical Computer Science}, keywords = {2006, graph, model, network, random, small-world}, month = {April}, number = {1}, pages = {96--103}, posted-at = {2008-07-18 11:28:36}, priority = {0}, title = {Could any graph be turned into a small-world?}, url = {http://dx.doi.org/10.1016/j.tcs.2005.12.008}, volume = {355}, year = {2006} }

RIS record

TY - JOUR ID - citeulike:2497644 L3 - citeulike-article-id:2497644 TI - Could any graph be turned into a small-world? T2 - Complex Networks JF - Theoretical Computer Science VL - 355 IS - 1 SP - 96 EP - 103 N2 - 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. KW - 2006 KW - graph KW - model KW - network KW - random KW - small-world AU - Duchon, Philippe AU - Hanusse, Nicolas AU - Lebhar, Emmanuelle AU - Schabanel, Nicolas PY - 2006/04/06/ UR - http://dx.doi.org/10.1016/j.tcs.2005.12.008 ER -

RIS BibTeX