vive wrote: > This does not work because (IMHO) you confuse location on the circle with > location in the network. Kleinbergs model gives efficient greedy routing > since there is a good balance between #connections going to different parts > of the graph.
I understand the difference; when I use the word "location" I'm usually talking about routing location, ie position on the circle - if I mean position in the network I try to use the word "topology", but I probably forget often enough to make it unclear. What I'm claiming is that if you replace (not add) nodes using the Kleinberg model, ie remove a node, add a new node, and connect it to each existing node with probability inversely proportional to the distance between their current locations on the circle, then eventually you will get a Kleinberg graph, regardless of what you started with, because eventually the graph you started with will have been completely replaced. This isn't true for all graph models, only those where the connection probabilities are independent. > But something similar that is exactly how I've been doing it: for a number > of steps add a small fraction of nodes. These new nodes randomize their > positions after getting links according to distribution on the "original" > locations in the topology. Then all nodes in the network swap for a while, > and then these new nodes leave again. The topology is still the same, but > the positions taken by nodes left in the network may have changed since > nodes that leave bring out some of the positions.. > > This scenario corresponds roughly to many nodes that are alive in the > network and a small flow through of positions by nodes joining but decide > to leave for good. Some results soon... OK, I guess we have different ideas about churn - in your model it's always the new nodes that leave, whereas in my model every node leaves eventually (though not necessarily after an equal amount of time). > My point with the experiment was: even if we dont shuffle positions then > it will still degrade the network if too many nodes are added. True, but there's a difference between adding 1000 nodes at once and replacing 1000 nodes one by one. I don't need to be convinced that routing would break if 1000 people joined at once! > Yes, if you dont shuffle anything and just replace nodes then you will move > between instantiations if you use the original positions. > > This is not the same as adding edges based on the current /positions/ that > nodes take after randomizing and swapp If swapping has restored the network to approximately the right distribution of edge lengths, then I suggest that using the current locations is approximately the same as using the original locations. But even if it's not the same, churn will eventually make the network navigable anyway, as long as the new edges have the right length distribution. > I understand what you mean, but to let nodes use other node locations on the > /circle/ to base their decisions on who in the /network/ to link to, then the > other node locations need to reflect the network. This is not preserved when > randomizing, and swapping can only bring it back to an approximation. That would apply if you were adding one node to a shuffled network and then waiting for swapping to restore the network to navigability. In that case I completely agree that you should use the original locations when connecting the new node, otherwise the new connections will be essentially random and won't be useful for navigation. But if you're constantly adding *and removing* nodes, then it's not necessarily important for the new links to be navigable using the old locations: what's important is for the new links to be navigable using the new locations, because eventually all the old links that were navigable using the old locations will be removed, and only the new locations will be relevant. In other words, make the node findable in the network that's being created, not in the network that's being destroyed. But again I guess this comes down to a difference of opinion about the nature of churn: does churn replace old nodes, or just add and remove new nodes? Cheers, Michael
