[p2p-hackers] clustering

[Michael Rogers]

Ranus wrote:
> 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[1].

> 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 
figures?

Cheers,
Michael

[1] http://fleece.ucsd.edu/~massimo/Journal/SWorld-Submission.pdf