Abstract
In stochastic exploration of geometrically embedded graphs, intuition suggests that providing a shortcut between a pair of nodes reduces the mean first passage time of the entire graph. Counterintuitively, we find a Braess’s paradox analog. For regular diffusion, shortcuts can worsen the overall search efficiency of the network, although they bridge topologically distant nodes. We propose an optimization scheme under which each edge adapts its conductivity to minimize the graph’s search time. The optimization reveals a relationship between the structure and diffusion exponent and a crossover from dense to sparse graphs as the exponent increases.
Funding Information
  • National Science Foundation (PHY-1554887)
  • Simons Foundation (568888)
  • University of Pennsylvania Materials Research Science and Engineering Center (DMR-1720530)

This publication has 38 references indexed in Scilit: