title: 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 differs from the value α(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 α(min) in the range [-1,-0.5], while disassortative networks have α(min) in the range [-0.5,0]. We derive an analytical relation between the degree correlation exponent ν and the optimal bias value α(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.
authors.affiliation: School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom and School of Business and Management, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom.
authors.forename: Moreno
authors.initials: M
authors.lastname: Bonaventura
authors.affiliation: School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom.
authors.forename: Vincenzo
authors.initials: V
authors.lastname: Nicosia
authors.affiliation: School of Mathematical Sciences, Queen Mary University of London, Mile End Road, London E1 4NS, United Kingdom and Dipartimento di Fisica e Astronomia, Università di Catania and INFN, 95123 Catania, Italy.
authors.forename: Vito
authors.initials: V
authors.lastname: Latora