Transport ad percolation in complex networks

Abstract

To design complex networks with optimal transport properties such as flow efficiency, we consider three approaches to understanding transport and percolation in complex networks. We analyze the effects of randomizing the strengths of connections, randomly adding longrange connections to regular lattices, and percolation of spatially constrained networks. Various real-world networks often have links that are differentiated in terms of their strength, intensity, or capacity. We study the distribution P(σ) of the equivalent conductance for Erdös-Rényi (ER) and scale-free (SF) weighted resistor networks with N nodes, for which links are assigned with conductance σi = e^-axi, where xi is a random variable with 0 < xi < 1. We find, both analytically and numerically, that P(σ) for ER networks exhibits two regimes: (i) For σ < e^-apc, P(σ) is independent of N and scales as a power law P(σ) ~ σ^(k)/a-1. Here pc = 1/(k) is the critical percolation threshold of the network and (k) is the average degree of the network. (ii) For σ > e^-apc, P(σ) has strong N dependence and scales as P(σ) ~ f(σ,apc/N^1/3). Transport properties are greatly affected by the topology of networks. We investigate the transport problem in lattices with long-range connections and subject to a cost constraint, seeking design principles for optimal transport networks. Our network is built from a regular d-dimensional lattice to be improved by adding long-range connections with probability Pij ~ rij^-α, where Tij is the lattice distance between site i and j. We introduce a cost constraint on the total length of the additional links and find optimal transport in the system for α = d + 1, established here for d = 1, 2 and 3 for regular lattices and df for fractals. Remarkably, this cost constraint approach remains optimal, regardless of the strategy used for transport, whether based on local or global knowledge of the network structure. To further understand the role that long-range connections play in optimizing the transport of complex systems, we study the percolation of spatially constrained networks. We now consider originally empty lattices embedded in d dimensions by adding long-range connections with the same power law probability p(r) ~ r^-α. We find that, for a ≤ d, the percolation transition belongs to the universality class of percolation in ER networks, while for α > 2d it belongs to the universality class of percolation in regular lattices (for one-dimensional linear chain, there is no percolation transition). However for d < α < 2d, the percolation properties show new intermediate behavior different from ER networks, with critical exponents that depend on α.