Topology-dependent density optima for efficient simultaneous network exploration

Abstract

A random search process in a networked environment is governed by the time it takes to visit every node, termed the cover time. Often, a networked process does not proceed in isolation but competes with many instances of itself within the same environment. A key unanswered question is how to optimise this process: how many concurrent searchers can a topology support before the benefits of parallelism are outweighed by competition for space? Here, we introduce the searcher-averaged parallel cover time (APCT) to quantify these economies of scale. We show that the APCT of the networked symmetric exclusion process is optimised at a searcher density that is well predicted by the spectral gap. Furthermore, we find that non-equilibrium processes, realised through the addition of bias, can support significantly increased density optima. Our results suggest novel hybrid strategies of serial and parallel search for efficient information gathering in social interaction and biological transport networks.

arXiv comment17 pages, 4 figures

References in corpus (19)

• Renormalization group analysis of the small-world network model
• Search in Power-Law Networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Intermittent search strategies
• Physics of Transport and Traffic Phenomena in Biology: from molecular motors and cells to organisms
• Global mean first-passage times of random walks on complex networks
• Large Deviations in Single File Diffusion
• Single-File diffusion in a Box
• The totally asymmetric simple exclusion process on networks
• Exact calculations of first-passage quantities on recursive networks
• Cover time for random walks on arbitrary complex networks
• Large deviations of a tracer in the symmetric exclusion process
• Optimal search strategies of run-and-tumble walks
• Exact distributions of the number of distinct and common sites visited by N independent random walkers
• Stochastic cycle selection in active flow networks
• Generic transport mechanisms for molecular traffic in cellular protrusions
• Diffusion of interacting particles in discrete geometries
• Optimality of spatially inhomogeneous search strategies
• Exact distributions of cover times for $N$ independent random walkers in one dimension

Cited by in corpus (1)

• First passage times of transport on planar spatial networks and their connections to off-network planar diffusion