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
