Cost of material or information flow in complex transportation networks

¹  Centro de Formação de Professores, Universidade Federal do Recôncavo da Bahia - 45.300-000, Amargosa, BA, Brazil
²  Departamento de Física, Instituto de Ciências Exatas, Universidade Federal de Minas Gerais - C. P. 702, 30161-970, Belo Horizonte, MG, Brazil

Corresponding authors: lauro@ufrb.edu.br jaff@fisica.ufmg.br

Received: 12 January 2010
Accepted: 30 April 2010

Abstract

To analyze the transport of information or material from a source to every node of a network, in a steady-state situation, we use two quantities introduced in the study of river networks: the cost and the flow. We study a network with K+1 nodes (the source plus K nodes) and M levels. The level of a node is defined as the number of links between the source and the node. We show that an upper bound to the global cost is C_0,max KM. From numerical simulations for spanning-tree networks with scale-free topology and with 10² up to 10⁷ nodes, it is found, for large K, that the average number of levels, the average level of the nodes, M , and the global cost are given by M ln(K), M ln(K) and C₀ K ln(K), respectively. These asymptotic results agree very well with the ones obtained from a mean-field approach. If the network is characterized by a degree distribution of connectivity P(k) k^-γ, we also find that the transport efficiency increases as long as γ decreases and that spanning-tree networks with scale-free topology are more optimized to transfer information or material than random networks.