Cover time for random walks on arbitrary complex networks

Physical Review E 96 (4), 042307


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.

llustration of our approach. Each node of the network is viewed as an independent entity that can be visited by the walker startingat the green node.
Benjamin F. Maier
Benjamin F. Maier

My research interests include the spread of infectious diseases, complex systems, and network theory

Dirk Brockmann
Dirk Brockmann

Head of Research on Complex Systems Group