Reachability on scale-free networks

Yagnik Goswami, M. S. Santhanam

Published 2015-01-06Version 1

Random walk on discrete lattices is a fundamental model in physics that forms the basis for our understanding of transport and diffusion process. In this work, we study unreachability in networks, {\it i.e}, the number of nodes not visited by any walkers until some finite time. We show that for the case of multiple random walkers on scale-free networks, the fraction of sites not visited is well approximated by a stretched exponential function. We also discuss some preliminary results for distinct sites visited on time-varying networks.