2007/01/09 by Bogdan Danila, Yong Yu, John A. Marsh +1 · 1 citation
Computer Science · Engineering · Mathematics · Physics and Astronomy · Social Sciences · #Algorithm #Average path length #Betweenness centrality #Complex Network Analysis Techniques #Complex network #Computation #Computer network #Computer science #Engineering #Equal-cost multi-path routing #Graph #Heuristic #K shortest path routing #Mathematical optimization #Mathematics #Node (physics) #Opinion Dynamics and Social Influence #Path (computing) #Private Network-to-Network Interface #Routing (electronic design automation) #Routing protocol #Shortest path problem #Static routing #Theoretical computer science #Transportation Planning and Optimization #cond-mat.dis-nn #cs.NI
paper · pdf · doi:10.1063/1.2731718
published as Chaos 17 (2), 026102 (2007) · 19 pages, 7 figures
arxiv created 2007/01/09 · openalex publication_date 2007/06/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.