Optimal search strategies on complex networks

Abstract

Complex networks are ubiquitous in nature and play a role of paramount importance in many contexts. Internet and the cyberworld, which permeate our everyday life, are self-organized hierarchical graphs. Urban traffic flows on intricate road networks, which impact both transportation design and epidemic control. In the brain, neurons are cabled through heterogeneous connections, which support the propagation of electric signals. In all these cases, the true challenge is to unveil the mechanisms through which specific dynamical features are modulated by the underlying topology of the network. Here, we consider 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. We show that an optimal combination of the two jump rules exists that maximises the efficiency of target search, the optimum reflecting the topology of the network.

arXiv commentSupplementary material is available on request

References in corpus (11)

• Emergence of scaling in random networks
• Intermittent search strategies
• Optimal search strategies for hidden targets
• Scaling theory of transport in complex networks
• Global mean first-passage times of random walks on complex networks
• Quantum Navigation and Ranking in Complex Networks
• Random Walks on deterministic Scale-Free networks: Exact results
• Noise-enhanced classical and quantum capacities in communication networks
• Efficient search by optimized intermittent random walks
• Trapping in complex networks
• Ring structures and mean first passage time in networks