Transport optimization on complex networks

DOI10.1063/1.2731718MaRDI QIDQ3624815zbMATH OpenOpenAlexWikidataFDO

Authors Bogdan Dănilă, Yong Yu, John A. Marsh, K. E. Bassler

Publication date 30 April 2009

Published in Chaos: An Interdisciplinary Journal of Nonlinear Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/0701184

Mathematics Subject Classification ID

Strange attractors, chaotic dynamics of systems with hyperbolic behavior (37D45)

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.

Cites work

• A critical point for random graphs with a given degree sequence
• A genetic algorithm for the weight setting problem in OSPF routing
• Collective dynamics of `small-world' networks
• Emergence of Scaling in Random Networks
• Finding good approximate vertex and edge partitions is NP-hard
• Introduction to algorithms
• Scaling in small-world resistor networks
• Statistical mechanics of complex networks

Cited in

(19)

• Finding the biased-shortest path with minimal congestion in networks via linear-prediction of queue length
• Optimisation of transportation service network using \(\kappa\)-node large neighbourhood search
• Traffic dynamics on complex networks: a survey
• Transportation network with externalities
• Distance-based routing strategy for traffic transport in spatial networks
• scientific article; zbMATH DE number 1688604 (Why is no real title available?)
• Self avoiding paths routing algorithm in scale-free networks
• Optimal network design for an on-demand transport system
• scientific article; zbMATH DE number 5524337 (Why is no real title available?)
• Communication network designing: transmission capacity, cost and scalability
• Introduction: Optimization in networks
• Improved efficient routing strategy on scale-free networks
• The self-adaptive routing strategy to alleviate packet loss in finite buffer networks
• Malleability of complex networks
• A distributed transportation simplex applied to a Content Distribution Network problem
• The impact of inner-coupling and time delay on synchronization: from single-layer network to hypernetwork
• Nonlinear transport network design
• The structure of branched transportation networks
• Optimal urban networks via mass transportation

This page was built for publication: Transport optimization on complex networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3624815)