Towards Design Principles for Optimal Transport Networks

We investigate the navigation problem in lattices with long-range connections and subject to a cost constraint. Our network is built from a regular two-dimensional ($d=2$) square lattice to be improved by adding long-range connections (shortcuts) with probability $P_{ij}\sim r_{ij}^{-\alpha }$, where $r_{ij}$ is the Manhattan distance between sites $i$ and $j$, and $\alpha$ is a variable exponent. We introduce a cost constraint on the total length of the additional links and find optimal transport in the system for $\alpha =d+1$ established here for $d=1$ and $d=2$. Remarkably, this condition remains optimal, regardless of the strategy used for navigation, being based on local or global knowledge of the network structure, in sharp contrast with the results obtained for unconstrained navigation using global or local information, where the optimal conditions are $\alpha =0$ and $\alpha =d$, respectively. The validity of our results is supported by data on the U.S. airport network.

Figure 1

Connections of a single node $i$. Each node $i$ has four short-range connections to its nearest neighbors ($a$, $b$, $c$, and $d$). A long-range directed connection may be placed to a random chosen node $j$.

Figure 2

Shortest-path length $\ell$ from each node to the central node in the network for different values of $\alpha$. In this case we impose a constraint in the length of the long-range connections. The sum of the length of these connections is limited, $\Lambda =\sum _{}^{}{r}_{ij}=N$, where $N$ is the number of nodes in the underlying lattice. The network model is constructed from a square lattice with $L^2$ nodes, with $L=256$. We can clearly observe that the best condition for shortest-path length is obtained for $\alpha =3$.

Figure 3

Average shortest-path length $⟨\ell ⟩$ as a function of $\alpha$. There is a constraint in the total length of the long-range connections, $\Lambda =\sum _{}^{}{r}_{ij}=L^2$, where $L$ is the size of the underlying square lattice. We find that the optimal shortest path is achieved for $\alpha =3$. With the restriction on total length, the number of long-range connections is not fixed (e.g., with $\alpha =0$, large long-range connections become frequent, which reduces the total number of long-range connections.) To obtain these results, we simulated 10 000 realizations for $L=512$, 3500 realizations for $L=1024$ and 2048, and 25 realizations for $L=4096$.

Figure 4

In (a) we show the average shortest-path length $⟨\ell ⟩$ as a function of the lattice size $L$ for the square lattice. The constraint in the total length of the long-range connections is $\Lambda =L^2$. The curve with $\alpha =3$ increases slower with $L$ compared to any other value of $\alpha$. In the inset, the plot of the successive slopes ${\delta }_S$ obtained from ${log}_{10}⟨\ell ⟩$ versus ${log}_{10}L$ reinforces the display of power-law behavior of $⟨\ell ⟩$ with $L$ for $\alpha \ne 3$. The plot of the successive slopes ${\gamma }_S$ obtained from ${log}_{10}⟨\ell ⟩$ versus ${log}_{10}({log}_{10}L)$ shown in (b) indicates that $⟨\ell ⟩$ increases as a power of the logarithm of $L$ for the optimal condition $\alpha =3$.

Figure 5

The characteristic average delivery time $⟨{\ell }_g⟩/L$ as a function of $\alpha$ for navigation with the greedy algorithm. The cost $\Lambda$ involved to add long-range connections changes the behavior of the density of long-range connections. As a result of that, a minimum is observed at $\alpha \approx 3$. Each data point is a result of 4000 simulations and the cost $\Lambda$ is fixed at $L^2$.