Kemeny-Braess paradox appears in random graphs at specific connectivity levels
The Kemeny-Braess Paradox in Random Graphs
Discrete MathematicsSocial and Information Networks
Summary
This work studies a puzzle in network behavior called the Braess paradox, where adding or removing certain links can unexpectedly slow down travel times. The authors focus on random graphs and identify exact connectivity thresholds where these surprising effects happen. They find that as networks get more connected, the paradox first appears for both adding and removing edges, then only for adding edges, and finally disappears in very dense networks. Their analysis uses mathematical tools involving random walks and spectral properties of graphs.
What this means in practice
- •For network designers: Identify when adding or removing connections in random networks will improve or degrade communication efficiency based on network density.
- •For urban traffic planners: Use thresholds for paradoxical effects to better predict how adding or closing roads affects average travel times in large, unpredictable network models.
A theory result. No direct application yet.
Authors
Manuel Bodirsky, Lorenzo Ciardo, Mihyun Kang
Abstract
In 2016, Kirkland and Zeng initiated the mathematical treatment of Braess paradox for random walks on graphs using Kemeny's constant as the measure of travel time. We study this phenomenon for the Erdős-Rényi random graph $G(n,p)$. An edge in a connected graph is called Kemeny-Braess if its deletion preserves connectedness and decreases Kemeny's constant, while a nonedge is Kemeny-Braess if its insertion increases Kemeny's constant. Let $\bar d=(n-1)p$ be the expected degree of $G\sim G(n,p)$, and assume that $\bar d-\log n\to\infty$, so that $G$ is connected with high probability. We determine the sharp asymptotic thresholds for the existence of both types of paradoxical behaviour. With $C^*=1/(1-\log 2)$, the threshold for Kemeny-Braess edges is $\bar d=C^*\log n$, whereas the threshold for Kemeny-Braess nonedges is $\bar d=2C^*\log n$. Hence, as the expected degree $\bar d$ increases, the connected regime exhibits three phases: first Kemeny-Braess paradox occurs for both edges and nonedges, then only for nonedges, and finally it disappears. In particular, in the dense regime, with high probability $G$ has no Kemeny-Braess edges or nonedges. This contrasts sharply with the spectral gap of the normalised Laplacian, for which Braess' paradox persists at constant edge density. Our proof combines a spectral-moment expansion of Kemeny's constant with uniform edge-perturbation estimates. Near the thresholds, the sign of the perturbation is governed by the endpoint degrees, and binomial large deviations yield the constant $C^*$ and the factor of two between the two thresholds.