Braess’s Paradox Analog in Physical Networks of Optimal Exploration
- 9 August 2024
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review Letters
- Vol. 133 (6) , 067401
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.Keywords
All Related Versions
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:
- Microvascular networks with uniform flowJournal of Theoretical Biology, 2019
- Effective graph resistanceLinear Algebra and its Applications, 2011
- Graph Spectra for Complex Networks2010
- A Guide to First-Passage Processes2001
- The random walk's guide to anomalous diffusion: a fractional dynamics approachPhysics Reports, 2000
- Collective dynamics of ‘small-world’ networksNature, 1998
- Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 AtomsThe Journal of Physical Chemistry A, 1997
- Paradoxical behaviour of mechanical and electrical networksNature, 1991
- Random walks on lattices. IV. Continuous-time walks and influence of absorbing boundariesJournal of Statistical Physics, 1973
- Sur les fonctions convexes et les inégalités entre les valeurs moyennesActa Mathematica, 1906