Back
to indexJon Kleinberg
Summary
The "small world phenomenon" states that everything is linked by short chains of acquaintances. These chains are referred to as social networks. However, this paper proves that a decentralized algorithm cannot always construct a shortest path between two points. This result is interesting since recent information retrieval methods are moving toward a autonomous agent model where each agent searches independant of its peers. This is demonstrated through the use of a 2D grid, where each vertex is connected to all its neighbors. Long range contacts are defined to be edges that are not immediately adjacent to the vertices. A decentralized algorithm may allow the development of chains that are independant of the grid, bypassing the short chains. The algorithm may never be able to find the shortest paths between points as a result. The proof shows that the decentralized algorithm is unable to use any 'clues' provided by the geometry of the grid.
Another interesting result is for the 'clustering component', r. When r = 0, all members of the grid are connected to their neighbors. As r increases, the number of long-range contacts formed independant of their position on the grid increases. With a 2D grid, Kleinberg proves that a lower bound of 2 is shown to be exactly the value where "there is a decentralized algorithm capable of producing chains whose length is a polynomial in log(n)". This basically means that the transmission time for a message over a network can be determined at this value of r only.
Methods
The proofs include lower and upper bound proofs for the r = 2 value, for different link distributions.
Keywords
small-world phenomenon, decentralized algorithm, message delivery time
Rating
8
Bibtex Entry
@article{ kleinberg99small,
author = "Jon Kleinberg",
title = "The small-world phenomenon: An algorithmic perspective",
journal = "Cornell Computer Science Technical Report",
volume = "1776",
number = "99",
year = "1999",
url = "http://www.cs.cornell.edu/home/kleinber/kleinber.html#papers"
}