# From the Physics of Interacting Polymers to Optimizing Routes on the London Underground

arXiv: https://arxiv.org/abs/1309.0745 · HTML: https://mlsanity.com/paper/1309.0745/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2013.

## Built on by (most cited first, 1 of 1)

- [Belief propagation for supply networks: Efficient clustering of their factor graphs](https://mlsanity.com/paper/2203.00467/) (2022)

## Abstract (arXiv)

Optimizing paths on networks is crucial for many applications, from subway traffic to Internet communication. As global path optimization that takes account of all path-choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing sub-optimal solutions. We employ the physics of interacting polymers and disordered systems to analyze macroscopic properties of generic path-optimization problems and derive a simple, principled, generic and distributed routing algorithm capable of considering simultaneously all individual path choices. We demonstrate the efficacy of the new algorithm by applying it to: (i) random graphs resembling Internet overlay networks; (ii) travel on the London underground network based on Oyster-card data; and (iii) the global airport network. Analytically derived macroscopic properties give rise to insightful new routing phenomena, including phase transitions and scaling laws, which facilitate better understanding of the appropriate operational regimes and their limitations that are difficult to obtain otherwise.