Cover time for random walks on arbitrary complex networks

Abstract

We present an analytical method for computing the mean cover time of a 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 in network topologies. Based on the global mean first passage time of target nodes we derive an estimate for the cumulative distribution function of the cover time based on first passage time statistics. We show that our result can be applied to various model networks, including Erdős-Rényi and Barabási-Albert networks, as well as various real-world networks. Our results reveal an intimate link between first passage and cover time statistics in networks in which structurally induced temporal correlations decay quickly and offer a computationally efficient way for estimating cover times in network related applications.

References in corpus (6)

• Cooperative Game Theory Approaches for Network Partitioning
• Hierarchical structure and the prediction of missing links in networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Learning Latent Block Structure in Weighted Networks
• Effective Distances for Epidemics Spreading on Complex Networks
• Mean first-passage time for random walks in general graphs with a deep trap

Cited by in corpus (18)

• Random walks and diffusion on networks
• Disentangling homophily, community structure and triadic closure in networks
• Large deviations of random walks on random graphs
• Map Equation Centrality: Community-aware Centrality based on the Map Equation
• Description of spreading dynamics by microscopic network models and macroscopic branching processes can differ due to coalescence
• Closed-form solutions to the dynamics of confined biased lattice random walks in arbitrary dimensions
• Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar
• Universal cover-time distribution of heterogeneous random walks
• Analytical results for the distribution of cover times of random walks on random regular graphs
• Dynamically accelerated cover times
• Optimal exploration of random walks with local bias on networks
• Modular hierarchical and power-law small-world networks bear structural optima for minimal first passage times and cover time
• Unexpected advantages of exploitation for target searches in complex networks
• Structural and temporal heterogeneities on networks
• Topology-dependent density optima for efficient simultaneous network exploration
• Active unidirectional network flow generates a packet molecular transport in cells
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• A Network Science Summer Course for High School Students