Optimal exploration of random walks with local bias on networks

We propose local-biased random walks on general networks where a Markovian walker is defined by different types of biases in each node to establish transitions to its neighbors depending on their degrees. For this ergodic dynamics, we explore the capacity of the random walker to visit all the nodes characterized by a global mean first passage time. This quantity is calculated using eigenvalues and eigenvectors of the transition matrix that defines the dynamics. In the first part, we illustrate how our framework leads to optimal exploration for small-size graphs through the analysis of all the possible bias configurations. In the second part, we study the most favorable configurations in each node by using simulated annealing. This heuristic algorithm allows obtaining approximate solutions of the optimal bias in different types of networks. The results show how the local bias can optimize the exploration of the network in comparison with the unbiased random walk. The methods implemented in this research are general and open the doors to a broad spectrum of tools applicable to different random walk strategies and dynamical processes on networks.