Characteristic times of biased random walks on complex networks

Abstract

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 $ν$ 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.

18 pages, 14 figures, 1 table