Biased random search in complex networks

Abstract

We study two types of biased random walk over complex networks, which are based on local information. In the first approach, the transitions towards neighboring nodes with smaller degrees are favored. We show analytically that for well connected networks, biasing the random walk based on inverse of nodes’ degrees leads to a uniform distribution of the visiting frequency, which arguably helps in speeding up the search. The second approach explores a random walk with a onestep memory with two-hop paths arrival balancing. We introduce a framework based on absorbing Markov chains for theoretical calculation of the mean first passage time in random walk with memory and apply it in the second approach. Numerical simulations indicate that both approaches can reduce the mean searching time of the target. The one-step memory based method proved to be better for undirected networks, while the inverse-degree biasing leads to faster search in directed networks.