Effect of Congestion Costs on Shortest Paths Through Complex Networks

We analyze analytically the effect of congestion costs within a physically relevant, yet exactly solvable, network model featuring central hubs. These costs lead to a competition between centralized and decentralized transport pathways. In stark contrast to conventional no-cost networks, there now exists an optimal number of connections to the central hub in order to minimize the shortest path. Our results shed light on an open problem in biology, informatics, and sociology, concerning the extent to which decentralized versus centralized design benefits real-world complex networks.

Figure 1

(a) Our model network showing transport pathways through the central hub (connections of length $1/2$ denoted by thick lines) and around the ring (connections of length 1 denoted by thin lines). Graph shows average shortest path length between any two nodes in a $n=1000$ node ring, with a cost per connection to the hub of $k=1$. There is an optimal value for the number of connections ($\rho \equiv pn\approx 44$) such that the average shortest path length $\overline{\ell }$ is a minimum. We denote this minimal shortest path length as $\overline{\ell }\equiv \overline{\ell }{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}$. (b) Photon scintillation image showing the nutrient density distribution within a laboratory-grown fungus Phanerochaete velutina.

Figure 2

Minimal shortest path length $\overline{\ell }{|}_{\mathrm{m}\mathrm{i}\mathrm{n}}$ (i.e., minimum value of $\overline{\ell }$) as obtained from Eq. (5). (a) Optimal number of connections $\rho \equiv pn$ as a function of the cost-per-connection $k$ to the hub. Results are shown for $n=1000$ and $n=10000$. (b) Optimal number of connections $\rho$ as a function of the network size. Results are shown for $k=2$ and $k=4$.

Figure 3

Examples of the scaled probability distribution for a network with $N=2$ hubs, where the two hubs have associated costs for traveling through them. In (a), ${\rho }_p=20$ and ${\rho }_q=10$ while the costs are $c_p=0.15$ and $c_q=0.05$. In (b), ${\rho }_p=50$ and ${\rho }_q=10$ while the costs are $c_p=0.35$ and $c_q=0.05$.