The mean random cover time for various search strategies follows a logarithmic, versus linear, growth pattern

Reporting in Chaos: An Interdisciplinary Journal of Nonlinear Science, a group of mathematicians in China and Australia demonstrate that the mean random cover time (MRCT) – the expected search time to find several search targets given in advance during a random search process – follows a logarithmic, versus linear, and proportional growth pattern against the number of search targets in random search processes.

The authors describe their iterative and pluralized, or multi-object, search approach to defining and analyzing the MRCT of complex networks, which links the gap of search time transiting from a single target search to the exhaustive search. For example, the authors illustrate the global MRCT, the expected time for a walker to start from a source node and randomly reach six distinct nodes in an independent multi-object search, in the “Yeast” network. Specifically, for each time step, the walker moves from current node i to node j with the transition probability p(i,j). Their theoretical results, validated by Monte Carlo simulations, show how the source site functions independently against the number of search targets.

The researchers confirm that the global MRCT follows a logarithmic growth pattern with respect to the number of targets on various synthetic and real networks. Utilizing the annealed network approach and the Sherman-Morrison formula, they explain the universal logarithmic growth pattern across various search strategies like generic, biased, and maximal entropy random walks.

Coauthor Tongfeng Weng states that the logarithmic growth pattern may serve as a universal principle governing multi-target searches and that this broad range of stochastic processes calls for additional research on multi-target searches on networks.

Source: “Multitarget search on complex networks: A logarithmic growth of global mean random search time,” by Tongfeng Weng, Jie Zhang, Michael Small, Ji Yang, Farshid Hassani Bijarbooneh, and Pan Hui, Chaos: An Interdisciplinary Journal of Nonlinear Science (2017). The article can be accessed at https://doi.org/10.1063/1.4990866 .