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

Abstract

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.

6 pages, 6 figures. Supplementary information available at: http://www.pnas.org/content/suppl/2013/07/29/1301111110.DCSupplemental

Cited by in corpus (28)

• Comprehensive routing strategy on multilayer networks
• Fluctuations in percolation of sparse complex networks
• Levy random walks on multiplex networks
• Solving the undirected feedback vertex set problem by local search
• Shortest node-disjoint paths on random graphs
• Network extraction by routing optimization
• Designing optimal networks for multi-commodity transport problem
• Color-avoiding percolation
• Sustainable optimal transport in multilayer networks
• Optimal redundancy against disjoint vulnerabilities in networks
• The edge-disjoint path problem on random graphs by message-passing
• Multicommodity routing optimization for engineering networks
• Cohesive urban bicycle infrastructure design through optimal transport routing in multilayer networks
• Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Scalable Node-Disjoint and Edge-Disjoint Multi-wavelength Routing
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• Coverage versus Supply Cost in Facility Location: Physics of Frustrated Spin Systems
• The global benefit of randomness in individual routing on transportation networks
• Bilevel optimization in flow networks: A message-passing approach
• Optimal transport with constraints: from mirror descent to classical mechanics
• Ultrametricity of optimal transport substates for multiple interacting paths over a square lattice network
• Optimally coordinated traffic diversion by statistical physics
• Belief propagation for supply networks: Efficient clustering of their factor graphs
• Integer Traffic Assignment Problem: Algorithms and Insights on Random Graphs
• Adaptive strategies for route selection en-route in transportation networks
• Bandwidth Allocation and Resource Adjustment for Stability Enhancement in Complex Networks
• Learning the optimally coordinated routes from the statistical mechanics of polymers