Cover time for random walks on arbitrary complex networks

Abstract

We present an analytical method for computing the mean cover time of a discrete-time random walk process on arbitrary, complex networks. The cover time is defined as the time a random walker requires to visit every node in the network at least once. This quantity is particularly important for random search processes and target localization on network structures. Based on the global mean first-passage time of target nodes, we derive a method for computing the cumulative distribution function of the cover time based on first-passage time statistics. Our method is viable for networks on which random walks equilibrate quickly. We show that it can be applied successfully to various model and real-world networks. Our results reveal an intimate link between first-passage and cover time statistics and offer a computationally efficient way for estimating cover times in network-related applications.