On Sun, Aug 19, 2007 at 11:34:48PM +0100, Michael Rogers wrote: > vive wrote: > > Try to see the network from the Kleinberg model as a platonian ideal form. > > We can try to replicate it by running the swapping algorithm, where nodes > > will > > prefer positions based on how they clustered in the original network, but > > the > > generated positioning will never (for all practical timescales) be more > > than a > > shadow of the perfect network. Hopefully it works rather well (surpringly > > well > > in simulation! :)) but still with its small faults and glitches in the > > assignments which affects the routing. > > Two points: first, the Kleinberg model is probabilistic, so even an > ideal network generated according to the model will have glitches.
Being probabilistic doesnt mean it can't work to 100% for a given instance. (you can let the HTL be large enough to route through the whole base graph in the original model) > (Hence Oskar's simulations show a success rate less than 100% even > before the positions are randomised.) That doesn't follow just because its probabilistic. This depends on simulations mostly not using the deterministic component of the Kleinberg model: the nearest-neighbor connections, which is unreasonable to assume for Freenet. So the greedy routing isn't able to strictly approach its target, having to deal with dead ends. > There are really no ideal Kleinberg networks: there are only more-or-less > Kleinbergish networks. Let's not get stuck on definitions. :-) My point still holds: you dont get back to the same energy level in a reasonable amount of time. A good approximation is what can be hoped for with the swapping algorithm. > Second, you can use the Kleinberg model to attach a new node to any > network, even if it isn't a Kleinberg network: just attach the new node > to each existing node with a probability inversely proportional to the > distance. (Likewise you can use the Erdos-Renyi model to add a node to > any network even if it isn't an Erdos-Renyi network: attach the new node > to each existing node with equal probability, etc.) You're right, we can use the inversely proportional distribution to add the edges. But lets say we have shuffled the positions randomly. Do you think this will help us to get a navigable network when we have added enough of nodes? I claim this is not the same thing. The random graph model works exactly because its uniformly at random, so you get short paths but not greedy routing working well. > >> Why would the connections between the other nodes make a difference? > > > > Sorry, I didn't understand that. > > Sorry, I meant why would you need to consider the existing connections > when connecting a new node? The connection probabilities are independent. Because they were generated under another configuration of the positions. To clarify what I mean, I performed some experiments on this in the "ideal model", no position randomizing. Edges were selected as in the Kleinberg model, evaluation was over 100000 routes with HTL=100. 1) Starting with 1000 nodes, average degree=10 Result: N=1000,succrate=0.996,avglen=8.261 2) Starting with 1000 nodes, average degree=10. Then we add 1000 nodes to random places on the circle (growing it to 2000 positions) with avgdeg=10 Result: N=2000,succrate=0.557,avglen=13.455 3) Starting with 2000 nodes, average degree=10 Result: N=2000,succrate=0.993,avglen=10.103 Comparing 2) and 3) we can see that generating the whole network from the start is not the same way as growing it with adding new nodes randomly *after* some nodes have already set up their edges. This happens since the system grows. The idea is that applying the model when considering links that have to be in the /whole/ network is a different thing than joining nodes later on and adding these /as/ the Kleinberg model. This is why the Kleinberg model is not good for explaining the /growth/ of navigable networks, but it works well to describe what ought to be when they are formed. regards, Vilhelm -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 187 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20070820/0f329a18/attachment.pgp>
