[p2p-hackers] clustering

Ranus networksimulator at gmail.com
Wed Mar 8 16:38:58 UTC 2006

About your previous mail: I checked the definition of clustering
<http://en.wikipedia.org/wiki/Clustering_coefficient> coefficient, that of a
chord vertex is 3/(n-2) (for a 2^n node ring), and it's the same for every
vertex, so the overall clustering coefficient is not high when n is
moderately large.

The definition of small-world is indeed clustering and short path.

Well, the network defined by Kleinberg falls into the category of
"scale-free networks". In such networks there are a few nodes that connect
to abundant other nodes. Following the power law distribution of degrees is
one way to construct scale-free networks, which are also small-world
networks. But there could be scale-free networks that are not small worlds.
(E.g, two star networks connected at the centers, here the clustering
coefficient is 0 because there's no triangle)

On the other hand, a very famous illustration of a small world is a regular
lattice with a few extra, randomly chosen edges. This does not conform the
power law distribution of edges and there's no supernode, but it's a small

Am I going too far from the point? Better turn around here...

The scale-free networks seem quite appealing as performance and scalability
are concerned, and it's simpler to guarantee short paths with powerful
supernodes. Many P2P applications such as Gia (Making Gnutella-like P2P
Systems Scalable, Sigcomm'03) introduce such supernodes to improve the
scalability. But it seems harder, to build scalable networks with more or
less the same number of edges for each node (this could be realistic when
edges are interpreted as connections, rather than links/routing
information), because at such time the supernodes are no where to be found.

I think some work could be done here... what do you suggest?

Ranus Yue
Tsinghua University

·¢¼þÈË: p2p-hackers-bounces at zgp.org [ <mailto:p2p-hackers-bounces at zgp.org>
mailto:p2p-hackers-bounces at zgp.org] ´ú±í Michael Rogers
·¢ËÍʱ¼ä: 2006Äê3ÔÂ8ÈÕ 16:36
ÊÕ¼þÈË: Peer-to-peer development.
Ö÷Ìâ: Re: [p2p-hackers] clustering

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.


[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>
p2p-hackers mailing list
p2p-hackers at zgp.org
Here is a web page listing P2P Conferences:

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://zgp.org/pipermail/p2p-hackers/attachments/20060309/9bf072ff/attachment.html

More information about the P2p-hackers mailing list