On Fri, Oct 3, 2008 at 5:36 PM, Matthew Toseland <toad at amphibian.dyndns.org>wrote:
> On Friday 03 October 2008 17:27, Michael Rogers wrote: > > Can't remember whether this has been raised before, but a random walk > > terminates at a given node with probability proportional to the node's > > degree; does this mean high-degree nodes are more likely to receive swap > > requests than low-degree nodes? Seems like that could be disruptive in > > two ways: > > > > 1) When a high-degree node changes its location, many other nodes are > > affected. > > > > 2) There might be some correlation between degree and other properties: > > high-degree darknet nodes might belong to committed users with large > > stores, in which case it's particularly disruptive if those nodes keep > > moving. > > > > Just a thought. > > I don't know. This looks like a question for vive/oskar. Yes, what Roger says is (more or less) correct. At least in the limit, the random walk will be at any vertex with probability proportional to its degree. One can weigh it back so that the limit is uniform over the vertices, but all the ways I know of doing it hurt the mixing time also. I would probably want to simulate different methods to see whether such just not terminating at high degree vertices is better than weighting the walk. // oskar -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20081004/a3fb0925/attachment.html>
