(Sorry for calling you Roger. :-) ) On Sat, Oct 4, 2008 at 3:41 PM, Michael Rogers <m.rogers at cs.ucl.ac.uk>wrote:
> Oskar Sandberg wrote: > > 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. > > I came across a paper yesterday which seems to achieve what we want - it > selects nodes uniformly at random using short walks. I haven't finished > reading it yet though, so there may be caveats. The key idea is to > accept the next step of the walk, from x to y, with probability > min(deg(x)/deg(y),1); otherwise the walk remains at x for another step: That is the Metropolis-Hastings chain. I was going to mention that, but I don't want to sound like a one trick pony suggesting MH as the solution to everything. I'm not sure it makes much sense to use one MH chain inside another, though. We are already doing one "accept if r < min(1, ... )" step, so an option is to multiply the above accept probability (deg(x)/deg(y)) into that one when choosing whether or not accept the change. // oskar -------------- next part -------------- An HTML attachment was scrubbed... URL: <https://emu.freenetproject.org/pipermail/tech/attachments/20081005/1d59b789/attachment.html>
