The Competition for Shortest Paths on Sparse Graphs
arXiv:1202.0213 · doi:10.1103/PhysRevLett.108.208701
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.
arXiv comment4 pages, 4 figures
References in corpus (12)
- Search in Power-Law Networks
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Optimal routing on complex networks
- Path finding strategies in scale-free networks
- Transport in weighted networks: Partition into superhighways and roads
- Glass models on Bethe lattices
- Resilience and rewiring of the passenger airline networks in the United States
- Minimum spanning trees on random networks
- Stability of shortest paths in complex networks with random edge weights
- Statistical Mechanics of Steiner trees
- Equilibration through local information exchange in networks
- Optimal Location of Sources in Transportation Networks
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