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.
authors.affiliation: Nonlinearity and Complexity Research Group, School of Engineering and Applied Science, Aston University, Birmingham B4 7ET, United Kingdom. chbyeung@gmail.com
authors.forename: Chi Ho
authors.initials: CH
authors.lastname: Yeung
authors.forename: David
authors.initials: D
authors.lastname: Saad
authors.forename: K Y Michael
authors.initials: KY
authors.lastname: Wong
mesh_terms: D000465:Algorithms; D001359:Aviation; D020407:Internet; D008962:Models, Theoretical; D011108:Polymers / Q000378:metabolism*; D011890:Railroads; D013598:Systems Theory
chemical_list: D011108:Polymers
references.citation: Nature. 2011 May 12;473(7346):167-73
references.pmid: 21562557
references.citation: Phys Rev Lett. 1989 May 22;62(21):2425-2428
references.pmid: 10039985
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2007 Jun;75(6 Pt 2):066112
references.pmid: 17677330
references.citation: Phys Rev Lett. 2000 May 15;84(20):4745-8
references.pmid: 10990786
references.citation: Nature. 2010 May 6;465(7294):53-9
references.pmid: 20445623
references.citation: Phys Rev E Stat Nonlin Soft Matter Phys. 2001 Aug;64(2 Pt 2):026118
references.pmid: 11497662
references.citation: Phys Rev Lett. 2007 Feb 23;98(8):088702
references.pmid: 17359138
references.citation: Science. 2002 Aug 2;297(5582):812-5
references.pmid: 12089451
references.citation: Phys Rev Lett. 2012 May 18;108(20):208701
references.pmid: 23003195
references.citation: Phys Rev Lett. 1996 Apr 8;76(15):2734-2737
references.pmid: 10060775