From the physics of interacting polymers to optimizing routes on the London Underground

Chi H. Yeung, David Saad, K.Y. Michael Wong

Research output: Contribution to journalArticle

Abstract

Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use 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 all individual path choices simultaneously. We demonstrate the efficacy of the 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, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.

Original languageEnglish
Pages (from-to)13717-13722
Number of pages6
JournalProceedings of the National Academy of Sciences
Volume110
Issue number34
Early online date29 Jul 2013
DOIs
Publication statusPublished - 20 Aug 2013

Fingerprint

Physics
Polymers
Internet
Railroads
Airports
Ostreidae
Phase Transition
Communication

Cite this

@article{570c1cb1ece14e5caa810c97dd1c060e,
title = "From the physics of interacting polymers to optimizing routes on the London Underground",
abstract = "Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use 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 all individual path choices simultaneously. We demonstrate the efficacy of the 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, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.",
author = "Yeung, {Chi H.} and David Saad and Wong, {K.Y. Michael}",
year = "2013",
month = "8",
day = "20",
doi = "10.1073/pnas.1301111110",
language = "English",
volume = "110",
pages = "13717--13722",
journal = "Proceedings of the National Academy of Sciences",
issn = "0027-8424",
number = "34",

}

From the physics of interacting polymers to optimizing routes on the London Underground. / Yeung, Chi H.; Saad, David; Wong, K.Y. Michael.

In: Proceedings of the National Academy of Sciences, Vol. 110, No. 34, 20.08.2013, p. 13717-13722.

Research output: Contribution to journalArticle

TY - JOUR

T1 - From the physics of interacting polymers to optimizing routes on the London Underground

AU - Yeung, Chi H.

AU - Saad, David

AU - Wong, K.Y. Michael

PY - 2013/8/20

Y1 - 2013/8/20

N2 - Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use 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 all individual path choices simultaneously. We demonstrate the efficacy of the 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, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.

AB - Optimizing paths on networks is crucial for many applications, ranging from subway traffic to Internet communication. Because global path optimization that takes account of all path choices simultaneously is computationally hard, most existing routing algorithms optimize paths individually, thus providing suboptimal solutions. We use 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 all individual path choices simultaneously. We demonstrate the efficacy of the 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, that facilitate better understanding of the appropriate operational regimes and their limitations, which are difficult to obtain otherwise.

UR - http://www.scopus.com/inward/record.url?scp=84882762337&partnerID=8YFLogxK

U2 - 10.1073/pnas.1301111110

DO - 10.1073/pnas.1301111110

M3 - Article

VL - 110

SP - 13717

EP - 13722

JO - Proceedings of the National Academy of Sciences

JF - Proceedings of the National Academy of Sciences

SN - 0027-8424

IS - 34

ER -