Characteristic times of biased random walks on complex networks

We consider degree-biased random walkers whose probability to move from a node to one of its neighbors of degree k is proportional to k(alpha), where alpha is a tuning parameter. We study both numerically and analytically three types of characteristic times, namely (i) the time the walker needs to come back to the starting node, (ii) the time it takes to visit a given node for the first time, and (iii) the time it takes to visit all the nodes of the network. We consider a large data set of real-world networks and we show that the value of alpha which minimizes the three characteristic times differs from the value alpha(min) = -1 analytically found for uncorrelated networks in the mean-field approximation. In addition to this, we found that assortative networks have preferentially a value of alpha(min) in the range [-1, -0.5], while disassortative networks have alpha(min) in the range [-0.5,0]. We derive an analytical relation between the degree correlation exponent. and the optimal bias value alpha(min), which works well for real-world assortative networks. When only local information is available, degree-biased random walks can guarantee smaller characteristic times than the classical unbiased random walks by means of an appropriate tuning of the motion bias.