Topology-dependent density optima for efficient simultaneous network exploration
Wilson, Daniel B
Baker, Ruth E
Physical Review E - Statistical, Nonlinear, and Soft Matter Physics
American Physical Society
MetadataShow full item record
Wilson, D. B., Baker, R. E., & Woodhouse, F. G. (2018). Topology-dependent density optima for efficient simultaneous network exploration. Physical Review E - Statistical, Nonlinear, and Soft Matter Physics, 97 (062301) https://doi.org/10.1103/PhysRevE.97.062301
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.
This work was supported by the EPSRC Systems Biology DTC Grant No. EP/G03706X/1 (D.B.W.), a Royal Society Wolfson Research Merit Award (R.E.B.), a Leverhulme Research Fellowship (R.E.B.), the BBSRC UK Multi-Scale Biology Network Grant No. BB/M025888/1 (R.E.B. and F.G.W.), and Trinity College, Cambridge (F.G.W.).
External DOI: https://doi.org/10.1103/PhysRevE.97.062301
This record's URL: https://www.repository.cam.ac.uk/handle/1810/280480