Mean First-Passage Dynamics in Complex Networks: Braess-Type Transitions and Perturbative Spectral Estimators

Braess' paradox in transportation networks is a prototypical example of the effect of graph topology on search time, where bad edges can increase the search time of a graph. Analytical derivations for the mean first-passage time (MFPT) of random walkers have enabled the analysis of search processes via spectral theory. However, direct evaluation of these spectral formulas is costly for large graph structures, and obscures how local rewiring shifts global search performance. Here, we harness known spectral representations and introduce perturbative, matrix-free estimators that scale to large, sparse graph topologies to further study the Braess paradox transition. We derive first-order corrections to node-averaged MFPTs under edge addition, pruning, and weight changes, to evaluate Braessian edge-behavior. We illustrate the approach on homogeneous cyclic graph structures, as well as Erdos-Renyi, Barabasi-Albert, and Watts-Strogatz graph structures, highlighting the interplay between edge length and network connectivity on the emergence of the Braess transition. Our results turn spectral MFPT theory into a practical tool for understanding optimal search processes of large networks, with particular applications to living matter (e.g. biological neural networks, vascular transport, mycorrhizal nutrient transport).