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

DOI10.1073/PNAS.1301111110MaRDI QIDQ5170973zbMATH OpenOpenAlexWikidataFDO

Authors C. H. Yeung, K. Y. M. Wong, David Saad

Publication date 25 July 2014

Published in Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.0745

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Internet topics (68M11) Statistical mechanics of polymers (82D60) Deterministic network models in operations research (90B10) Programming involving graphs or networks (90C35)

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.

Recommendations

• Networking -- a statistical physics perspective
• Network routing
• Traffic optimization in transport networks based on local routing
• Asymptotic optimality of shortest path routing algorithms
• Route optimization in IP networks

Cites work

• A note on two problems in connexion with graphs
• An implementation of linear and nonlinear multicommodity network flows
• Greedy distributed optimization of multi-commodity flows
• Information, Physics, and Computation
• On a routing problem
• Solving a Time-Space Network Formulation for the Convoy Movement Problem
• Statistical Physics of Spin Glasses and Information Processing
• The maximum concurrent flow problem
• Unfoldings of quasi-periodic tori in reversible systems

Cited in

(7)

• Navigability of interconnected networks under random failures
• Shortest node-disjoint paths on random graphs
• Bandwidth allocation and resource adjustment for stability enhancement in complex networks
• Self-organization scheme for balanced routing in large-scale multi-hop networks
• Adaptive strategies for route selection en-route in transportation networks
• Minimum connected dominating set and backbone of a random graph
• Re-routing game: the inadequacy of mean-field approach in modeling the herd behavior in path switching

Describes a project that uses

Uses Software

• NetDraw

This page was built for publication: From the physics of interacting polymers to optimizing routes on the London underground

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5170973)