Re: Random walks

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:

http://www.barsoom.org/papers/ton-2007-sampling.pdf

They also add backtracking to ensure that churn doesn't produce a bias
towards short-lived nodes.

Cheers,
Michael