=?gb2312?B?tPC4tDogW3AycC1oYWNrZXJzXSBjbHVzdGVyaW5n?=

[Ranus]

Well... Small-world is characterized by both a high clustering degree =
and a
short average path length. While DHTs are designed to have short paths =
from
node to node, they do not necessarily present clustering.=20

I just thought about Chord... The nodes keep track of neighbors every =
2^n
steps away. I don't think the nodes are clustering here, or am I wrong
somewhere?


--
Ranus Yue
Tsinghua University

-----=D3=CA=BC=FE=D4=AD=BC=FE-----
=B7=A2=BC=FE=C8=CB: p2p-hackers-bounces at zgp.org =
[mailto:p2p-hackers-bounces at zgp.org] =B4=FA
=B1=ED Daniel Stutzbach
=B7=A2=CB=CD=CA=B1=BC=E4: 2006=C4=EA3=D4=C28=C8=D5 12:56
=CA=D5=BC=FE=C8=CB: p2p-hackers at zgp.org
=D6=F7=CC=E2: Re: [p2p-hackers] clustering

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=20
> characteristics, at least not in the overlay network view of things,=20
> 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=20
> 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=20
> 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.

--=20
Daniel Stutzbach                           Computer Science Ph.D Student
http://www.barsoom.org/~agthorr                     University of Oregon
_______________________________________________
p2p-hackers mailing list
p2p-hackers at zgp.org
http://zgp.org/mailman/listinfo/p2p-hackers
_______________________________________________
Here is a web page listing P2P Conferences:
http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences