Multitarget search on complex networks: A logarithmic growth of global mean random cover time
arXiv:1701.03259 · doi:10.1063/1.4990866
Abstract
We investigate multitarget search on complex networks and derive an exact expression for the mean random cover time that quantifies the expected time a walker needs to visit multiple targets. Based on this, we recover and extend some interesting results of multitarget search on networks. Specifically, we observe the logarithmic increase of the global mean random cover time with the target number for a broad range of random search processes, including generic random walks, biased random walks, and maximal entropy random walks. We show that the logarithmic growth pattern is a universal feature of multi-target search on networks by using the annealed network approach and the Sherman-Morrison formula. Moreover, we find that for biased random walks, the global mean random cover time can be minimized, and that the corresponding optimal parameter also minimizes the global mean first passage time, pointing towards its robustness. Our findings further confirm that the logarithmic growth pattern is a universal law governing multitarget search in confined media.
References in corpus (23)
- Emergence of scaling in random networks
- Community structure in social and biological networks
- Lethality and centrality in protein networks
- Finding community structure in networks using the eigenvectors of matrices
- Cooperative Game Theory Approaches for Network Partitioning
- The large-scale organization of metabolic networks
- Critical phenomena in complex networks
- Localization of maximal entropy random walk
- Biased random walks on complex networks: the role of local navigation rules
- First passages in bounded domains: When is the mean first passage time meaningful?
- First passages for a search by a swarm of independent random searchers
- Optimizing persistent random searches
- Characteristic times of biased random walks on complex networks
- Exact calculations of first-passage quantities on recursive networks
- Random walk and trapping processes on scale-free networks
- Effective target arrangement in a deterministic scale-free graph
- Exact calculations of first-passage properties on the pseudofractal scale-free web
- Mean first-passage time for maximal-entropy random walks in complex networks
- Optimal and suboptimal networks for efficient navigation measured by mean-first passage time of random walks
- Maximal entropy random walk in community finding
- Autocatalytic reaction on low-dimensional substrates
- Numerical evidence against a conjecture on the cover time of planar graphs
- Random Walks on Complex Networks