Efficient routing on complex networks

We propose a routing strategy to improve the transportation efficiency on complex networks. Instead of using the routing strategy for shortest path, we give a generalized routing algorithm to find the so-called efficient path, which considers the possible congestion in the nodes along actual paths. Since the nodes with the largest degree are very susceptible to traffic congestion, an effective way to improve traffic and control congestion, as our strategy, can be redistributing traffic load in central nodes to other noncentral nodes. Simulation results indicate that the network capability in processing traffic is improved more than 10 times by optimizing the efficient path, which is in good agreement with the analysis.

Figure 1

The order parameter $H$ vs $R$ for two-dimensional lattice (a) and BA networks (b) with the same size $N=1225$. The routing algorithm at the shortest path yields $R_{\mathrm{lattice}}\approx 65$ and $R_{\mathrm{BA}}\approx 4.0$.

Figure 2

(Color online). The critical $R_c$ vs $\beta$ for scale-free networks with size $N=1225$. Both Simulation and analysis indicate that the maximum of $R_c$ corresponds to $\beta \approx 1.0$. The data shown here are the average over 10 independent runs.

Figure 3

The load distribution when congestion occurs for a BA network with size $N=1225$. (a) The case of $\beta =0$ where $R_c=4.0$ and we set $R=10$. (b) The case of $\beta =1$ where $R_c=45$ and we set $R=60$.

Figure 4

(Color online) (a) The average actual path length $L_{\mathrm{av}}$ vs the network size $N$ under various values of $\beta$, by using the efficient path routing. (b) and (c) show $⟨T⟩$ and $NH$ vs $R$ for $\beta =0.0$ and 1.0, respectively, where $N=1225$.