Decentralized navigation of multiple packages on transportation networks

We investigate by numerical simulation and finite-size analysis the impact of long-range shortcuts on a spatially embedded transportation network. Our networks are built from two-dimensional ($d=2$) square lattices to be improved by the addition of long-range shortcuts added with probability $P\left(r_{ij}\right)\sim r_{ij}^{-\alpha }$ [J. M. Kleinberg, Nature 406, 845 (2000)]. Considering those improved networks, we performed numerical simulation of multiple discrete package navigation and found a limit for the amount of packages flowing through the network. Such a limit is characterized by a critical probability of creating packages $p_c$, where above this value a transition to a congested state occurs. Moreover, $p_c$ is found to follow a power law, $p_c\sim L^{-\gamma }$, where $L$ is the network size. Our results indicate the presence of an optimal value of ${\alpha }_{\min }\approx 1.7$, where the parameter $\gamma$ reaches its minimum value and the networks are more resilient to congestion for larger system sizes. Interestingly, this value is close to the analytically found value of $\alpha$ for the optimal navigation of single packages in spatially embedded networks, where ${\alpha }_{\mathrm{opt}}=d$. Finally, we show that the power spectrum for the number of packages navigating the network at a given time step $t$, which is related to the divergence of the expected delivery time, follows a universal Lorentzian function, regardless of the topological details of the networks.

Figure 1

Kleinberg networks are built by adding long-range connections on regular lattices. For a given node $i$, a node $j$ is randomly chosen and an undirected link of length $r_{ij}$ is added between them with probability $P\left(r_{ij}\right)\sim r_{ij}^{-\alpha }$. By doing so, the node $j$ can be any node with a Manhattan distance of $r_{ij}$. The dashed lines highlight the eight nodes separated from node $i$ by a lattice distance $r=2$. We randomly choose the node $j$ from this set of eight nodes.

Figure 2

Transition to congested phases for different values of $\alpha$. In (a) we show the order parameter $\eta$ as a function of the probability of creating new packages $p$. When the network topology favors the decentralized delivery algorithm, the packages are delivered at a higher rate than new packages are created, avoiding nodes becoming overloaded, therefore preventing congestion. This is the case for $\alpha =0$, 1, and 2, where the transition occurs for higher values of $p$. As depicted in (b), the critical threshold $p_c$ marks a maximum value on the response susceptibility $\chi$. Here, we use $L=128$ with $T={10}^4$ for each value of $\alpha$ and simulation time equal to ${10}^5$.

Figure 3

Behavior of the critical point $p_c$. In panel (a) we show the critical probability $p_c$ as a function of the exponent $\alpha$. As the system size $L$ increases, the packages take longer to be delivered, causing the increase of $\mathrm{\Delta }N$. As a consequence of that, the transition to congested phases occurs for even smaller values of $p_c$. However, independently of the value of $L$, the critical probability always presents a maximum as $\alpha$ approaches the value of $\alpha =2$. The critical probabilities follow a power-law behavior, $p_c\sim L^{-\gamma }$, as presented in the main plot of (b). The values of the exponent $\gamma$ resulting from a least-square fitting to the data are presented in the inset, where a nonmonotonic behavior can be clearly observed. Here, we use $L=2^5$ with $T={10}^4$ for each value of $\alpha$ and simulation time equal to ${10}^5$.

Figure 4

(a) Power spectrum of $S$ as a function of $f$ for $\alpha =0$, and for the free phase, $p<p_c$. As one can see, for all values of the rescaled control parameter $\varepsilon$, $S$ has the form of a Lorentzian function given by Eq. (6). The values of $\varepsilon$ increase from the top to the bottom. Therefore, the curves at the top are closer to the critical value $p_c$. Provided there is Lorentzian behavior, one expects a power-law decay of $S$ for larger values of $f$, as shown by the dashed line with slope $-2$. (b) Intensity $I$ as a function of the order parameter $\varepsilon$ obtained from the nonlinear curve fitting of $S$ using Eq. (6), for different values of $\alpha$ in the free phase. The plot suggests that $I\sim {\varepsilon }^{-\zeta }$. For $\alpha =3$ and 4, the estimated values of $I$ deviates from this behavior when the system approaches the transition at the lower values of $\varepsilon$. The solid lines are the fitting results using $I\sim {\varepsilon }^{-\zeta }$ in the ranges of $\varepsilon$ where such power-law behavior holds. Each power spectrum is obtained through an average of 100 realizations, with $L=32$ and simulation time equal to ${10}^5$.

Figure 5

Data collapse of the power spectrum $S$ for different values of the control parameter $\varepsilon$ and (a) $\alpha =0$, (b) $\alpha =1$, (c) $\alpha =2$, (d) $\alpha =3$, and (e) $\alpha =4$. We use $\zeta =2.2\left(0\right)$, 2.3(3), 2.6(0), 2.9(1), and 3.0(9) for $\alpha =0$, 1, 2, 3, and 4, respectively. These values were obtained from a least-squares fitting to the data presented in Fig. 4. The inset in each plot shows the original data for the power spectrum $S$ obtained from our simulations. (f) When the plot axes are scaled using $S{\varepsilon }^{\zeta }/I_0$ and $\left(f/f_0\right){\varepsilon }^{-\zeta /2}$, all data presented in panels (a)–(e) collapse into the universal Lorentzian function $\mathcal{L}$. Each power spectrum is obtained through an average of 100 realizations, with $L=32$ and simulation time equal to ${10}^5$.