The Competition for Shortest Paths on Sparse Graphs

Abstract

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of non-linear overlap cost that penalizes congestion. Routing becomes increasingly more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. A distributed linearly-scalable routing algorithm is devised. The ground state of such systems reveals non-monotonic complex behaviors in both average path-length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers.

4 pages, 4 figures

References in corpus (2)

• Optimal routing on complex networks
• Statistical Mechanics of Steiner trees

Cited by in corpus (20)

• From the Physics of Interacting Polymers to Optimizing Routes on the London Underground
• Networking - A Statistical Physics Perspective
• Shortest node-disjoint paths on random graphs
• Sustainable optimal transport in multilayer networks
• The edge-disjoint path problem on random graphs by message-passing
• Multicommodity routing optimization for engineering networks
• The Futility of Being Selfish -- The Impact of Selfish Routing on Uncoordinated and Optimized Transportation Networks
• Infrastructure adaptation and emergence of loops in network routing with time-dependent loads
• Scalable Node-Disjoint and Edge-Disjoint Multi-wavelength Routing
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• The global benefit of randomness in individual routing on transportation networks
• Coverage versus Supply Cost in Facility Location: Physics of Frustrated Spin Systems
• The network source location problem: ground state energy, entropy and effects of freezing
• Optimal transport with constraints: from mirror descent to classical mechanics
• Ultrametricity of optimal transport substates for multiple interacting paths over a square lattice network
• Bilevel optimization in flow networks: A message-passing approach
• Optimally coordinated traffic diversion by statistical physics
• Learning the optimally coordinated routes from the statistical mechanics of polymers
• Enhancing speed of pinning synchronizability: low-degree nodes with high feedback gains
• Integer Traffic Assignment Problem: Algorithms and Insights on Random Graphs