Fast Mixing Markov Chains. The mixing time of a random walk determines the efficiency of the sampling. On the practical side, the mixing time of RW in many OSNs was found larger than commonly believed [1]}. Multiple dependent random walks [2]}
have been used to sample disconnected and loosely connected graphs.
Random walks with jumps have been used to sample large graphs in [3]}, [4]} and in [5]}. All the above methods treat all nodes with equal importance, which is orthogonal to our technique.
