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α, where α 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 α which minimizes the three characteristic times is different from the value αrm 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 αrm min in the range [-1,-0.5], while disassortative networks have αrm min in the range [-0.5, 0]. We derive an analytical relation between the degree correlation exponent nu and the optimal bias value αrm 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.