A Braess paradox analog in optimal search networks.

What is the optimal network architecture to minimize the time it takes for a random walker to find a randomly selected target node? A low first encounter time is the key to successful exploration both for diffusion in real space, like the motion of a protein inside a living cell and for the stochastic transitions in an energy landscape. Intuition suggests that adding a shortcut between the random walk's starting and target nodes will reduce the pair's mean first passage time. Considering the mean first passage time between all pairs, one would assume that a topologically well-connected network would be optimal. Counterintuitively, we find that this is not always the case. We show a Braess paradox analog in the case of diffusive exploration in spatially embedded graphs in which the transit time through an edge scales as the mean squared displacement of the random walk through the edge. For regular diffusion a shortcut longer than the average edge length of the graph can deteriorate the overall search efficiency of the network, although it bridges topologically distant nodes. Ultimately, to investigate the interplay between the graph structure and anomalous diffusion, we propose an optimization scheme according to which each edge can adapt its conductivity until the graph's average pairwise mean first passage time is minimized. The optimization reveals a crossover in the network's architecture: for super-diffusive motion, the optimal graph is small-world, while for sub-diffusive propagation short-range networks are optimal. We believe that this optimization approach might give insights to investigate the mechanisms that highly optimized biological systems employ to solve the problem of efficient exploration in various length scales.