[p2p-hackers] clustering

[Michael Rogers]

Gary Jefferson wrote:
> Just a general question for the list: DHTs don't
> exhibit small-world characteristics, at least not in
> the overlay network view of things, right?

That depends on your definition of 'small world'. Most people take it to 
mean short paths and high clustering, but as far as I know the Freenet 
work uses a more specific definition due to Jon Kleinberg: a graph is a 
small world if it can be embedded in a metric space such that the length 
of the edges follows a power law distribution, where the magnitude of 
the power law exponent is equal to the number of dimensions in the 
metric space[1]. Kleinberg showed that greedy routing in such a graph is 
efficient, but if the power law exponent has any other value then greedy 
routing is inefficient[2,3]. However, it's also possible that the length 
distribution doesn't follow a power law at all (eg Chord, where the 
length distribution is exponential and greedy routing is efficient).

Most DHTs aren't small worlds in the sense used in the Freenet work; 
Symphony[4] is an exception.

Cheers,
Michael

[1] http://www.cs.cornell.edu/home/kleinber/nips14.ps
[2] http://www.cs.cornell.edu/home/kleinber/nat00.pdf
[3] http://www.cs.cornell.edu/home/kleinber/swn.pdf
[4] http://www-db.stanford.edu/~bawa/Pub/symphony.pdf