David Saad (Aston University)
Polymer physics for route optimisation on the London underground
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 optimise paths individually, thus providing sub-optimal solutions. This work includes two different aspects of routing. In the first [1] we employ the cavity approach to study analytically the routing of nodes on a graph of given topology to predefined network routers and devise the corresponding distributive optimisation algorithm. In the second [2] we employ the physics of interacting polymers and disordered systems (the replica method) to analyse macroscopic properties of generic path-optimisation problems between arbitrarily selected communicating pairs; we also derive a simple, principled, generic and distributive routing algorithm capable of considering simultaneously all individual path choices.
Two types of nonlinear interactions are considered with different objectives: 1) alleviate traffic congestion at both cyber and real space and provide better route planning; and 2) save resources by powering down non-essential and redundant routers/stations at minimal cost. This saves energy and man-power, and alleviates the need for investment in infrastructure. We show that routing becomes more difficult as the number of communicating nodes increases and exhibits interesting physical phenomena such as ergodicity breaking. The ground state of such systems reveals non-monotonic complex behaviours in average path-length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers.
We demonstrate the efficacy of the new algorithm [2] 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.
[1] C. H. Yeung, D. Saad, The Competition for Shortest Paths on Sparse Graphs, Phys. Rev. Lett., 108, 208701 (2012).
[2] C. H. Yeung, D. Saad and K. Y. M. Wong, From the Physics of Interacting Polymers to Optimizing Routes on the London Underground, submitted (2012).