Optimal search strategies on complex networks

Summary

This work considers agents randomly hopping along the links of a graph, with the additional possibility of performing long-range hops to randomly chosen disconnected nodes with a given probability, and shows that an optimal combination of the two jump rules exists that maximises the efficiency of target search.

Keywords

Jump, Computer science, Topology (electrical circuits), Complex network, Network topology

References

Random walks on complex networks.Jae Dong Noh, Heiko Rieger — 2003
Dynamical Processes on Complex NetworksAlain Barrat, Marc Barthélemy, Alessandro Vespignani — 2008
Google's PageRank and BeyondAmy N. Langville, Carl D. Meyer — 2006
Intermittent search strategiesOlivier Bénichou, Claude Loverdo, Manon Moreau — 2011
Global mean first-passage times of random walks on complex networks.Vincent Tejedor, Olivier Bénichou, Raphaël Voituriez — 2009
Global first-passage times of fractal lattices.Christophe P. Haynes, Anthony P. Roberts — 2008
Optimal search strategies for hidden targets.Olivier Bénichou, Mathieu Coppey, Manon Moreau — 2005
Generalized facilitated diffusion model for DNA-binding proteins with search and recognition states.Maximilian Bauer, Ralf Metzler — 2012
Noise-enhanced classical and quantum capacities in communication networks.Filippo Caruso, Susana F. Huelga, Martin B. Plenio — 2010
Matrix Algorithms: Volume 1, Basic DecompositionsJames R. Schott, G. W. Stewart — 1998
Random walks on deterministic scale-free networks: exact results.Elena Agliari, Raffaella Burioni — 2009
A Google-like model of road network dynamics and its application to regulation and controlEmanuele Crisostomi, Steve Kirkland, Robert Shorten — 2011
Ring structures and mean first passage time in networks.Andrea Baronchelli, Vittorio Loreto — 2005
Mean first-passage time for maximal-entropy random walks in complex networksYuan Lin, Zhongzhi Zhang — 2014
Search researchMichael F. Shlesinger — 2006
Effect of trap position on the efficiency of trapping in treelike scale-free networksZhongzhi Zhang, Lin Yuan, Youjun Ma — 2011
The Anatomy of a Large-Scale Hypertextual Web Search EngineSergey Brin, Lawrence M. Page — 1998
Efficient search by optimized intermittent random walksGleb Oshanin, Katja Lindenberg, Horacio S. Wio — 2009
How a protein searches for its site on DNA: the mechanism of facilitated diffusionLeonid A. Mirny, Michael Slutsky, Zeba Wunderlich — 2009
Flexible search tactics and efficient foraging in saltatory searching animalsW. John O’Brien, Barbara I. Evans, Howard I. Browman — 1989

Cited by

Search optimization, funnel topography, and dynamical criticality on the string landscapeJustin Khoury, Onkar Parrikar — 2019

Related papers

A survey on topologies of multilevel converters and study of two novel topologiesChenchen Wang, Yondong Li — 2009
Generating realistic ISP-level network topologiesOliver Heckmann, Michael Piringer, Johannes Schmitt — 2003
Mathematical analysis of function and mechanism of run-up and take-off in the long jumpKening Zou — 2011
Process of the continuous cross-jump and the movement error in early childhoodKimihiro Fujimaki — 1989
Basic overconstrained topologies with schönflies motionsG. Gogu — 2014
Analysis the Proportion of Three Jump of the Male Distance Jump Sportsman on the World NowdayHongyu Wang — 2006
Improving networks using group-based topologiesJaime Lloret, Carlos E. Palau, Fernando Boronat — 2008
A Secondary Study Examining the Effectiveness of Network Topologies: The Case of Ring, Bus, and Star TopologiesS Keliwar — 2020
Compare Research on Take-off Effect of Drop-jump and Approach JumpXiong An-zhu — 2007