About your previous mail: I checked the definition of clustering
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 world.
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
-----邮件原件-----
发件人: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]] 代表 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.
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
_______________________________________________
p2p-hackers mailing
list
[EMAIL PROTECTED]
http://zgp.org/mailman/listinfo/p2p-hackers
_______________________________________________
Here is a web page
listing P2P Conferences:
http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
_______________________________________________ p2p-hackers mailing list [EMAIL PROTECTED] http://zgp.org/mailman/listinfo/p2p-hackers _______________________________________________ Here is a web page listing P2P Conferences: http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
