Optimal transport on complex networks

Transport optimization is a problem encountered in connection to many different types of complex networks, including biological networks, social networks, and a variety of natural and human-made transport and communication networks. We present results for transport optimization on random, scale-free, as well as geometric networks, obtained using a novel heuristic algorithm. Some of the results have been published in Phys.Rev.\ E {\bf 74}, 046106 (2006). Our algorithm balances transport by adjusting traffic routing at every iteration to minimize the betweenness of the busiest node on the network. This is done with the least possible lengthening of the paths passing through that node. Our results are compared with those obtained using classical shortest path routing, as well as previously proposed network transport optimization algorithms. We show that routing produced by our algorithm enables networks to sustain significantly higher traffic without jamming than in the case of any previously proposed routing optimization algorithm. Furthermore, we show that, in spite of unavoidable lengthening of the average path, the small-world character of network routing is preserved.