Popularity-driven random walks on a class of scale-free graphs

This paper introduces a class of random walks on graphs in which the probability of moving from a vertex u to one of its neighbors v is proportional to d_{v}^{α}, where d_{v} is the degree of v and α a parameter that characterizes the walk. We derive the stationary distribution of the walks and study their expected behavior in the class of Barabasi-Albert random graphs. We find that the fastest exploration of the graph is for α<0, that is, when there is a bias towards neighbors of low degree. This bias balances the bias of the degree distribution, leading to a uniform probability of being on a given vertex at a given time, thus leading to a faster exploration.