[p2p-hackers] clustering

[Daniel Stutzbach]

On Tue, Mar 07, 2006 at 07:43:39PM -0800, 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?  I mean,
> from each node's perspective, it might look a bit like
> a small world -- in Kademlia, for instance, my routing
> tables will center around my own ID space.  

DHTs typically are small worlds.

The small-world characteristics are short path lengths (comparable to
a random graph) and high clustering (much more than a random graph).

DHTs certainly have short path lengths (that's the point).  All the
DHTs I can think of also have high clustering.  A node's neighbors are
likely to also be neighbors.

> But the network, as a whole, isn't small world, and isn't vulnerable
> to vertex-order attacks, right?  Or am I missing something?

I believe you are thinking of power-law graphs (also called
"scale-free") which have a few very-high-degree peers that make juicy
targets.  Power-law graphs frequently (but don't necessarily) exhibit
small-world characteristics.  Almost everyone is connected to some of
the high-degree peers who are all connected together, so there is a
lot of clustering.  The high degree peers also provide short-paths
everywhere.  As a result, they're small worlds.

However, not all small-worlds are power-law graphs.  In particular,
DHTs are not power-law graphs.  There are not exceptionally high or
low degree peers.

-- 
Daniel Stutzbach                           Computer Science Ph.D Student
http://www.barsoom.org/~agthorr                     University of Oregon