On Tuesday, March 21, 2006
> I reran the same simulations I posted before, this time scaling
> up the degrees with the size of the network (2 log_2 N edges per
> node)...
Out of curiosity, what happens to the phase transition with
this number of degrees? 1M meltdown was with 20 links, right? Does
this extra 2x avoid the phase transition at 1M nodes, and if so,
does it merely push it to say, 2M, or it is completely avoided
for all practical node counts (say, less than 10^12 or something)?
Best wishes -
S.Osokine.
21 Mar 2006.
-----Original Message-----
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED]
Behalf Of Oskar Sandberg
Sent: Tuesday, March 21, 2006 12:19 PM
To: Peer-to-peer development.
Subject: Re: Big hype on small worlds. (was Re: Dijjer and Freenet(RE:
[p2p-hackers] clustering))
Bob Harris wrote:
>
> But you can't make a a division between "small-world networks"
> and DHTs, because all DHTs are, as has been noted, small-world
networks,
> just with varying degrees of randomness.
>
>
> Oskar: I don't think you realize that your use of the word "small world"
> is quite
> different from everyone else's and the graph theoretic definition. If you
> think CAN defines a small world in any sense, we will not be able to
> communicate.
I don't know if somebody using the term "small-world network" got your
grant money or something, but you need to get over your fixation with
having your own definition for this term, and be more specific about
what you do not like. As far as I can tell, your problem seems to be
with trying to use the Kleinberg model (and further developments on it)
to build probabilistic DHT networks. This is a particular model, which
really has nothing to do with Watz and Strogatz, "theoretician wannabes"
or "crackpot physicists".
> I guess the success of the "small worlds" meme owes a lot to having a
> catchy
> name, a loose allusion to human behavior, and a model simple enough that
> anyone, including theoretician wannabes and even crackpot physicists, to
> get
> into the p2p game. When performance is not an issue or when one cannot tell
> X from X^2, every approach is as good as every other.
I don't know what part of "log^2 scaling when the node degree is
constant" it is that you do not understand, but it feels like a lost
cause trying to repeat it again. For the benefit of any other readers,
however, I reran the same simulations I posted before, this time scaling
up the degrees with the size of the network (2 log_2 N edges per node):
1000 4.6811
2000 5.0803
4000 5.446
8000 5.7923
16000 6.1494
32000 6.561
64000 6.8694
128000 7.2843
256000 7.6469
512000 8.0424
For those who are to lazy to calculate the deltas, here is a plot:
http://www.math.chalmers.se/~ossa/temp/llog.png
What kind of scaling does that like to you? (Hint: what function gives a
straight line when the x-axis increases exponentially?)
But the fact that the number of edges can be scaled independently of the
size of the network is a STRENGTH of the randomized networks.
Prescribing a certain number of edges for a certain N is dumb, because
more edges can mean quicker lookups, so there is no reason for nodes to
have less edges then they can manage. In the randomized networks every
edge is helpful, but no edge is necessary.
The bigger point is, however, that staring oneself blind at the
asymptotic order of the scaling is the silly behavior of people whose
reasoning is limited to "5 << 25". One should look at the size window
that one can expect the network to grow to, consider acceptable values
for other parameters like node degree, and pick the appropriate
algorithm which performs well in that window.
// oskar
_______________________________________________
p2p-hackers mailing list
p2p-hackers@zgp.org
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
p2p-hackers@zgp.org
http://zgp.org/mailman/listinfo/p2p-hackers
_______________________________________________
Here is a web page listing P2P Conferences:
http://www.neurogrid.net/twiki/bin/view/Main/PeerToPeerConferences
