On the decentralized navigation of multiple packages on transportation networks

Abstract

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(r_{ij})\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 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.

7 pages, 5 figures

References in corpus (5)

• Navigability of Complex Networks
• Structural properties of spatially embedded networks
• Kleinberg Navigation in Fractal Small World Networks
• Exact Solution for Optimal Navigation with Total Cost Restriction
• Majority-vote model on spatially embedded networks: crossover from mean-field to Ising universality classes