Topology-dependent density optima for efficient simultaneous network exploration
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 optimis...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
American Physical Society
2018
|
| _version_ | 1797058136925798400 |
|---|---|
| author | Wilson, D Baker, R Woodhouse, F |
| author_facet | Wilson, D Baker, R Woodhouse, F |
| author_sort | Wilson, D |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-06T19:46:17Z |
| format | Journal article |
| id | oxford-uuid:2268c05d-b36d-4802-bbe1-44560cef06cb |
| institution | University of Oxford |
| last_indexed | 2024-03-06T19:46:17Z |
| publishDate | 2018 |
| publisher | American Physical Society |
| record_format | dspace |
| spelling | oxford-uuid:2268c05d-b36d-4802-bbe1-44560cef06cb2022-03-26T11:38:44ZTopology-dependent density optima for efficient simultaneous network explorationJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:2268c05d-b36d-4802-bbe1-44560cef06cbSymplectic Elements at OxfordAmerican Physical Society2018Wilson, DBaker, RWoodhouse, FA 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. |
| spellingShingle | Wilson, D Baker, R Woodhouse, F Topology-dependent density optima for efficient simultaneous network exploration |
| title | Topology-dependent density optima for efficient simultaneous network exploration |
| title_full | Topology-dependent density optima for efficient simultaneous network exploration |
| title_fullStr | Topology-dependent density optima for efficient simultaneous network exploration |
| title_full_unstemmed | Topology-dependent density optima for efficient simultaneous network exploration |
| title_short | Topology-dependent density optima for efficient simultaneous network exploration |
| title_sort | topology dependent density optima for efficient simultaneous network exploration |
| work_keys_str_mv | AT wilsond topologydependentdensityoptimaforefficientsimultaneousnetworkexploration AT bakerr topologydependentdensityoptimaforefficientsimultaneousnetworkexploration AT woodhousef topologydependentdensityoptimaforefficientsimultaneousnetworkexploration |