Big hype on small worlds. (was Re: Dijjer and Freenet (RE: [p2p-hackers] clustering))

[Bob Harris]

Hi Daniel,

I saw the earlier fruitless discussion on the definition of "small world"
networks.
Let me summarize my thoughts:

o You and Oskar may well be using the same definition.

o I suspect you have not read the papers you cite. The wikipedia article
is quite clear that small world networks are a subclass of random graphs.
The
paper is talking about random rewirings. Oskar and you agreed the other day
that _all_ DHTs form small world networks. Something is amiss.

o Take some DHT, say CAN. It decidedly does not fit the 'definition'
provided
by Watts and Strogatz.

o The definition provided by Watts and Strogatz is quite loose in the
first place.


o I also question why, if 'small worlds' were such an important,
fundamental,
defining characteristic of graphs, it took mankind until 1998 to come up
with a (catchy) name for them.

o I maintain that there is more hype here than substance.

But look, I don't _really_ care if you guys build systems with O(log^2 N)
lookup
time when better techniques are available. It just so happens that too much
noise misplaced in an area will creat a fog and lead people astray. But hey, at

the end of the day, it's someone else's problem. I saw 40+ hop simulations
and
felt the need to call it as I saw it.

Bob.


> Oskar and I seem to be using the same definition of "small world
> network", the same definition put forth by Watts and Strogatz when
> they defined the term, also the same as the definition given in
> Wikipedia, as well as in several books and peer-reviewed publications
> devoted to the topic. (http://en.wikipedia.org/wiki/Small-world_network,
> Watts, D. J. and S. H. Strogatz. 1998. "Collective dynamics of
> 'small-world' networks". Nature 393:440-42.
> http://tam.cornell.edu/SS_nature_smallworld.pdf)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://zgp.org/pipermail/p2p-hackers/attachments/20060321/8b3ddf8a/attachment.htm