Competition for Shortest Paths on Sparse Graphs

Optimal paths connecting randomly selected network nodes and fixed routers are studied analytically in the presence of a nonlinear overlap cost that penalizes congestion. Routing becomes more difficult as the number of selected nodes increases and exhibits ergodicity breaking in the case of multiple routers. The ground state of such systems reveals nonmonotonic complex behaviors in average path length and algorithmic convergence, depending on the network topology, and densities of communicating nodes and routers. A distributed linearly scalable routing algorithm is also devised.

Figure 1

(a) An example of the ground state of ${\mathcal{H}}^{\prime }$ with $\alpha =2$ in a simple network with 6 senders (●) and a single receiver (▵) among 20 nodes. Dashed lines correspond to idle links, while thin and thick solid lines correspond to communication loads of 1 and 2, respectively. To minimize ${\mathcal{H}}^{\prime }$, communication from the top left sender is routed through a long path. (b) A schematic diagram representing the derivation of Eq. (1).

Figure 2

Analytical results of $⟨E⟩$ and $⟨L⟩$ per communication as a function of $f_s$ on regular, ER, and SF networks and ER and SF networks with hub receivers, all with $⟨k⟩=3$ and $f_r=0.01$.

Figure 3

(a) Analytic $⟨L⟩$ values (solid lines) compared to simulation results (dashed lines, symbols) for regular networks with $⟨k⟩=3,4,5$, a single receiver, and $N=100$ nodes, averaged over 1000 realizations. (b) Algorithmic convergence time $⟨T_c⟩$ averaged over instances ($\approx 98\%$) which converge within $5\times {10}^4$ updates per node. Inset: $⟨T_c⟩$ as a function of $N$ for $⟨k⟩=3$, $f_s=0.2$, and a single receiver.

Figure 4

Phase diagram for fractions $f_s$ and $f_r$ of sender and receiver (router) nodes, respectively, and two types of receivers on regular and ER networks with random and hub receivers. (a) Senders with a fixed router allocation and (b) sender pairs with a flexible router choice.