The Kemeny-Braess Paradox in Random Graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.24143
curl -X POST /api/v1/records/arxiv/2610.24143/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.24143/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'