# Cover time for random walks on arbitrary complex networks

arXiv: https://arxiv.org/abs/1706.02356 · HTML: https://mlsanity.com/paper/1706.02356/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jun 2017.

## Built on by (most cited first, 5 of 5)

- [Disentangling homophily, community structure and triadic closure in networks](https://mlsanity.com/paper/2101.02510/) (2021)
- [Analyzing Modularity Maximization in Approximation, Heuristic, and Graph Neural Network Algorithms for Community Detection](https://mlsanity.com/paper/2310.10898/) (2023)
- [Heuristic Modularity Maximization Algorithms for Community Detection Rarely Return an Optimal Partition or Anything Similar](https://mlsanity.com/paper/2302.14698/) (2023)
- [Modularity maximisation for graphons](https://mlsanity.com/paper/2101.00503/) (2021)
- [Systematic assessment of the quality of fit of the stochastic block model for empirical networks](https://mlsanity.com/paper/2201.01658/) (2022)

## Abstract (arXiv)

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 ErdHos-R'enyi and Barab'asi-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.