Transport optimization on complex networks

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 and tested with numerical simulation 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.

• Publication year

  2007

• Venue

  Chaos

• Publication date

  2007-01-09

• Fields of study

  Medicine, Physics, Computer Science, Engineering

• Identifiers
  DOI 10.1063/1.2731718arXiv cond-mat/0701184PMID 17614689
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar, PubMed

• No claims are published for this paper.

• No concepts are published for this paper.

• Probability, Statistics and Queueing Theory with Computer Science Applications

  2014cited by this paper
• Structural bottlenecks for communication in networks.

  2007cited by this paper
• Congestion-gradient driven transport on complex networks

  2006cited by this paper
• Optimal routing on complex networks

  2006cited by this paper
• Load balancing in IP networks by optimising link weights

  2005cited by this paper
• Onset of traffic congestion in complex networks.

  2005cited by this paper
• Jamming in complex gradient networks.

  2005cited by this paper
• Scaling in small-world resistor networks

  2005cited by this paper
• Efficient routing on complex networks.

  2005cited by this paper
• Optimized network structure and routing metric in wireless multihop ad hoc communication

  2005cited by this paper
• Network dynamics: Jamming is limited in scale-free systems

  2004cited by this paper
• Improved routing strategies for Internet traffic delivery.

  2004cited by this paper
• Dynamics of jamming transitions in complex networks

  2004cited by this paper
• Effect of congestion costs on shortest paths through complex networks.

  2004cited by this paper
• An Incremental Procedure for Improving Path Assignment in a Telecommunications Network

  2003cited by this paper
• Competition-driven network dynamics: emergence of a scale-free leadership structure and collective efficiency.

  2003cited by this paper
• A Comparison of Heuristics for the Discrete Cost Multicommodity Network Optimization Problem

  2003cited by this paper
• Optimizing OSPF/IS-IS weights in a changing world

  2002cited by this paper
• Optimal network topologies for local search with congestion

  2002cited by this paper
• A Genetic Algorithm for the Weight Setting Problem in OSPF Routing

  2002cited by this paper
• Statistical mechanics of complex networks

  2001cited by this paper
• Scientific collaboration networks. I. Network construction and fundamental results.

  2001cited by this paper
• Introduction to algorithms [2nd ed.]

  2001cited by this paper
• Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality.

  2000cited by this paper
• Optimization with Extremal Dynamics

  2000cited by this paper
• Emergence of scaling in random networks

  1999cited by this paper
• Collective dynamics of ‘small-world’ networks

  1998cited by this paper
• A Critical Point for Random Graphs with a Given Degree Sequence

  1995cited by this paper
• Punctuated equilibrium and criticality in a simple model of evolution.

  1993cited by this paper
• Finding Good Approximate Vertex and Edge Partitions is NP-Hard

  1992cited by this paper
• Probability, Statistics, and Queueing Theory With Computer Sciences Applications (2nd ed.)

  1992cited by this paper

• Time series analysis of wildfire propagation in Chile: A complex networks approach

  2025cites this paper
• Understanding route choice behaviors' impact on traffic throughput in a dynamic transportation network

  2024cites this paper
• A Novel Reinforcement Learning Routing Algorithm for Congestion Control in Complex Networks

  2023cites this paper
• Adaptation to Fluctuating Neuronal Signal Traffic for Brain Connectivity

  2023cites this paper
• The influence of layered community network structure on traffic capacity

  2023cites this paper
• The impact of inner-coupling and time delay on synchronization: From single-layer network to hypernetwork.

  2022cites this paper
• The self-adaptive routing strategy to alleviate packet loss in finite buffer networks

  2021cites this paper
• NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020influential citation
• NC-MOPSO: A network centrality guided multi-objective particle swarm optimization for transport optimization on networks

  2020influential citation
• Routing optimization considering real-time traffic condition and travel distance

  2019cites this paper
• An optimal routing strategy for transport networks with minimal transmission cost and high network capacity

  2019cites this paper
• A Crowdsourcing Approach for Sustainable Last Mile Delivery

  2018cites this paper
• Network capacity enhancement with various link rewiring strategies

  2018cites this paper
• Implementing beneficial prioritization of traffic flow in complex networks

  2018cites this paper
• Mobility and Congestion in Dynamical Multilayer Networks with Finite Storage Capacity.

  2018cites this paper
• Efficient edge rewiring strategies for enhancement in network capacity

  2018cites this paper
• Malleability of complex networks

  2018cites this paper
• Improving the throughput of transportation networks with a time-optimization routing strategy

  2018influential citation
• Check-in based routing strategy in scale-free networks

  2017cites this paper
• Efficient path routing strategy for flows with multiple priorities on scale-free networks

  2017cites this paper
• Congestion control strategy on complex network with privilege traffic

  2017cites this paper
• Transport Capacity Limit of Urban Street Networks

  2017cites this paper
• Effective traffic-flow assignment strategy on multilayer networks.

  2017cites this paper
• An optimal routing strategy on scale-free networks

  2017cites this paper
• Effects of packet retransmission with finite packet lifetime on traffic capacity in scale-free networks

  2017cites this paper
• Efficient packet navigation method on scale-free networks with finite and diversiform node delivery capacity

  2016cites this paper
• Finding the biased-shortest path with minimal congestion in networks via linear-prediction of queue length

  2016cites this paper
• Constraints of nonresponding flows based on cross layers in the networks

  2016cites this paper
• Optimized routing strategy for complex network with multiple priorities

  2016cites this paper
• Prediction of Transportation Network Based on PageRank Algorithm

  2016cites this paper
• Enhancing traffic capacity of scale-free networks by link-directed strategy

  2016cites this paper
• Minimize Congestion for Random-Walks in Networks via Local Adaptive Congestion Control

  2016cites this paper
• Improved efficient routing strategy on two-layer complex networks

  2016cites this paper
• Traffic dynamics of information packets in complex networks with non-uniform source and destination selection

  2015cites this paper
• Enhancing traffic capacity of scale-free networks by employing hybrid routing strategy

  2015cites this paper
• Improved routing strategy based on gravitational field theory

  2015cites this paper
• Exploring highly-efficient routing strategy on scale-free networks with limited and diverse node capacity

  2015cites this paper
• Efficient packet transportation on complex networks with nonuniform node capacity distribution

  2015cites this paper
• Transport optimization considering the node aggregation ability

  2015cites this paper
• Network Resilience Improvement and Evaluation Using Link Additions

  2015cites this paper
• Maximum transport capacity of a network

  2015cites this paper
• Global dynamic routing for scale-free networks with heterogeneous node capacity

  2014cites this paper
• Cost-constrained and centrality-balanced network design improvement

  2014cites this paper
• Gravitational field routing strategy considering the distribution of traffic flow

  2014cites this paper
• An incremental optimal routing strategy for scale-free networks

  2014cites this paper
• Efficient routing on two layer degree-coupled networks

  2014cites this paper
• Effective strategy of adding links for improving network transport efficiency on complex networks

  2014cites this paper
• Effects of efficient edge rewiring strategies on network transport efficiency

  2014cites this paper
• Method to enhance traffic capacity for two-layer complex networks

  2014cites this paper
• Enhanced Flow in Small-World Networks

  2013cites this paper
• QUEUE RESOURCE REALLOCATION STRATEGY FOR TRAFFIC SYSTEMS IN SCALE-FREE NETWORK

  2013cites this paper
• Self Avoiding Paths Routing Algorithm in Scale-Free Networks

  2013cites this paper
• Optimal dynamic bandwidth allocation for complex networks

  2013cites this paper
• Enhancing Synchronizability of Complex Networks via Optimization

  2013cites this paper
• Distance-Based Routing Strategy for Traffic Transport in Spatial Networks

  2013cites this paper
• An adaptive strategy based on linear prediction of queue length to minimize congestion in Barabási—Albert scale-free networks

  2013cites this paper
• Incremental routing strategy on scale-free networks

  2013cites this paper
• Analysis of network traffic flow dynamics based on gravitational field theory

  2013cites this paper
• IMPROVING NETWORK TRANSPORT EFFICIENCY BY EDGE REWIRING

  2013cites this paper
• ENHANCING TRAFFIC CAPACITY OF TWO-LAYER COMPLEX NETWORKS

  2013cites this paper
• Dynamic Source Routing Strategy for Two-Level Flows on Scale-Free Networks

  2013cites this paper
• Optimizing Synchronization, Flow, and Robustness in Weighted Complex Networks

  2012cites this paper
• AN EFFICIENT BANDWIDTH ALLOCATION STRATEGY FOR SCALE-FREE NETWORKS

  2012cites this paper
• Traffic Dynamics on Complex Networks: A Survey

  2012cites this paper
• AN EFFICIENT WEIGHTED ROUTING STRATEGY FOR SCALE-FREE NETWORKS

  2012cites this paper
• IMPROVED EFFICIENT ROUTING STRATEGY ON SCALE-FREE NETWORKS

  2012cites this paper
• Efficient packet routing strategy in complex networks

  2012cites this paper
• Range-limited Centrality Measures in Complex Networks

  2011cites this paper
• Efficient routing strategies in scale-free networks with limited bandwidth

  2011cites this paper
• Epidemic metapopulation model with traffic routing in scale-free networks

  2011cites this paper
• Jamming in the weighted gradient networks

  2011cites this paper
• The effect of human rhythm on packet delivery

  2010cites this paper
• Optimization of transport protocols with path-length constraints in complex networks

  2010cites this paper
• Optimal resource allocation on heterogeneous complex transport networks

  2010cites this paper
• Optimal Capacity Allocation on Heterogeneous Complex Transport Networks

  2010cites this paper
• A temporal ant colony optimization approach to the shortest path problem in dynamic scale-free networks

  2010cites this paper
• Collectively optimal routing for congested traffic limited by link capacity.

  2009cites this paper
• Self-adjusting routing schemes for time-varying traffic in scale-free networks.

  2009cites this paper
• Networks: Structure and Dynamics

  2009cites this paper
• Integrating network structure and dynamic information for better routing strategy on scale-free networks

  2009cites this paper
• Large-scale curvature of networks.

  2009cites this paper
• Power grid vulnerability: a complex network approach.

  2008cites this paper
• Improved routing strategies for data traffic in scale-free networks

  2008cites this paper
• Decorrelation of networked communication flow via load-dependent routing weights

  2008cites this paper
• An image edge detection and segmentation algorithm based on small-world phenomenon

  2008cites this paper
• The effect of competition between two spatially separated markets - An investigation of two interlinked Bak-Sneppen models.

  2008cites this paper
• Geographic coarse graining analysis of the railway network of China

  2008cites this paper
• Gradient mechanism in a communication network.

  2007cites this paper
• Building catastrophes: networks designed to fail by avalanche-like breakdown

  2007cites this paper
• Introduction: optimization in networks.

  2007cites this paper
• Traffic dynamics in scale-free networks with limited buffers and decongestion strategy

  2007cites this paper
• Optimal transportation network with concave cost functions: loop analysis and algorithms.

  2007cites this paper