m.rogers at cs.ucl.ac.uk
Wed Mar 8 18:36:09 UTC 2006
> Well, the network defined by Kleinberg falls into the category of
> "scale-free networks".
Sorry to contradict you, but a scale-free network has a power law degree
distribution. A Kleinberg small world has a power law length
distribution, and there are no restrictions on the degree distribution.
> The scale-free networks seem quite appealing as performance and
> scalability are concerned, and it's simpler to guarantee short paths
> with powerful supernodes.
I've come across a couple of papers suggesting scale-free topologies for
P2P networks, but I'm a bit skeptical. Scale-free graphs typically have
O(log n) diameter, so if you flood O(sqrt n) advertisements from any
node and O(sqrt n) queries from any other node then the query is likely
to find the advertisement, but on the other hand the same's true of
random graphs, which don't depend on a small fraction of the nodes
handling a large fraction of the messages... I guess it's a question of
finding a degree distribution that matches the bandwidth distribution of
the nodes. Maybe that's power law, maybe not... does anyone have any
More information about the P2p-hackers