Distinct nodes visited by random walkers on scale-free networks

Random walks on discrete lattices are fundamental models that form the basis for our understanding of transport and diffusion processes. For a single random walker on complex networks, many properties such as the mean first passage time and cover time are known. However, many recent applications involving search engines and recommender systems involve multiple random walkers on complex networks. In this work, based on numerical simulations, we show that the fraction of nodes of scale-free network not visited by W random walkers in time t has a stretched exponential form independent of the number of walkers and the size of the network. This leads to a power-law relation between nodes not visited by W walkers and by 1 walker within time t. Thus the problem of finding the distinct nodes visited by W walkers, effectively, can be reduced to that of a single walker. The robustness of the results is demonstrated by verifying them on four different real-world networks that approximately display scale-free structure.