2017/01/31 by Tongfeng Weng, Jie Zhang, Michael Small +3 · 16 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · Physics and Astronomy · Social Sciences · #Algorithm #Complex Network Analysis Techniques #Computer science #Cover (algebra) #Diffusion and Search Dynamics #Entropy (arrow of time) #Evolutionary Game Theory and Cooperation #Logarithm #Logarithmic growth #Mathematical analysis #Mathematics #Physics #Random element #Random field #Random search #Random walk #Random walker algorithm #Robustness (evolution) #Statistical physics #Statistics #cs.SI #physics.soc-ph
paper · pdf · doi:10.1063/1.4990866
published in Chaos An Interdisciplinary Journal of Nonlinear Science 27(9), 093103 (American Institute of Physics)
openalex publication_date 2017/09/01 · arxiv created 2017/09/12 · arxiv updated 2017/09/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.