Weighted Random Walks for Sampling. Random walks on graphs with weighted edges, or equivalently reversible Markov chains [1]}, [2]}, are well studied and heavily used in Monte Carlo Markov Chain simulations [3]} to sample a state space with a specified probability distribution. However, to the best of our knowledge, WRWs have not been designed explicitly for measurements of real online systems. In the context of sampling OSNs, the closest works are [4]}, [5]}. Technically speaking, they use WRW. But they set as their only objective the minimization of the mixing time, which makes them orthogonal and complementary to our approach, as we discussed above.
