Intermittent exploration on a scale-free network

Institute for Advanced Studies in Basic Sciences - Zanjan 45195-1159, Iran and The Abdus Salam International Centre for Theoretical Physics - Strada Costiera 11, 34014 Trieste, Italy

Corresponding author: aramezan@ictp.it

Received: 27 August 2006
Accepted: 2 February 2007

Abstract

We study an intermittent random walk on a random network of scale-free degree distribution. The walk is a combination of simple random walks of duration t_w and random long-range jumps. While the time the walker needs to cover all the nodes increases with t_w, the corresponding time for the edges displays a nonmonotonic behaviour with a minimum for some nontrivial value of t_w. This is a heterogeneity-induced effect that is not observed in homogeneous small-world networks. The optimal t_w increases with the degree of assortativity in the network. Depending on the nature of degree correlations and the elapsed time the walker finds an over/under-estimate of the degree distribution exponent.