Transport optimization on complex networks
arXiv:cond-mat/0701184 · doi:10.1063/1.2731718
Abstract
We present a comparative study of the application of a recently introduced heuristic algorithm to the optimization of transport on three major types of complex networks. The algorithm balances network traffic iteratively by minimizing the maximum node betweenness with as little path lengthening as possible. We show that by using this optimal routing, a network can sustain significantly higher traffic without jamming than in the case of shortest path routing. A formula is proved that allows quick computation of the average number of hops along the path and of the average travel times once the betweennesses of the nodes are computed. Using this formula, we show that routing optimization preserves the small-world character exhibited by networks under shortest path routing, and that it significantly reduces the average travel time on congested networks with only a negligible increase in the average travel time at low loads. Finally, we study the correlation between the weights of the links in the case of optimal routing and the betweennesses of the nodes connected by them.
19 pages, 7 figures
References in corpus (14)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- Efficient routing on complex networks
- Optimal network topologies for local search with congestion
- Optimization with Extremal Dynamics
- Improved routing strategies for Internet traffic delivery
- Dynamics of jamming transitions in complex networks
- Optimal routing on complex networks
- Communication Bottlenecks in Scale-Free Networks
- Competition in Social Networks: Emergence of a Scale-free Leadership Structure and Collective Efficiency
- Effect of congestion costs on shortest paths through complex networks
- Congestion-gradient driven transport on complex networks
- Scaling in Small-World Resistor Networks
- Optimized network structure and routing metric in wireless multihop ad hoc communication
Cited by in corpus (16)
- Power grids vulnerability: a complex network approach
- The Large Scale Curvature of Networks
- Improved community structure detection using a modified fine tuning strategy
- Efficient routing strategies in scale-free networks with limited bandwidth
- Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity
- Comprehensive routing strategy on multilayer networks
- Collectively optimal routing for congested traffic limited by link capacity
- Congestion diffusion and decongestion strategy in networked traffic
- Enhanced Flow in Small-World Networks
- Optimization in Networks
- Optimal transport on wireless networks
- Optimization of transport protocols with path-length constraints in complex networks
- Self Avoiding Paths Routing Algorithm in Scale-Free Networks
- The Gradient Mechanism in a Communication Network
- Malleability of complex networks
- NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks