Abstract
In this paper, we reveal the relationship between entropy rate and the congestion in complex network and solve it analytically for special cases. Finding maximizing entropy rate will lead to an improvement of traffic efficiency, we propose a method to mitigate congestion by allocating limited traffic capacity to the nodes in network rationally. Different from former strategies, our method only requires local and observable information of network, and is low-cost and widely applicable in practice. In the simulation of the phase transition for various network models, our method performs well in mitigating congestion both locally and globally. By comparison, we also uncover the deficiency of former degree-biased approaches. Owing to the rapid development of transportation networks, our method may be helpful for modern society.
The Challenge of Network Congestion
Congestion is the primary barrier to efficiency in modern transportation and communication systems. Whether managing city traffic or internet data packets, the goal is to prevent bottlenecks that lead to gridlock. Traditional solutions often involve expensive infrastructure upgrades or complex routing algorithms that require global, real-time knowledge of the entire network.
This research addresses the capacity allocation problem: given a limited budget to upgrade specific nodes (e.g., adding lanes to a road or processing power to a server), how can we identify the most impactful locations? The authors propose a solution that relies solely on local observations, making it both cost-effective and practical for large-scale systems.
Methodology: Maximizing Entropy for Fluid Flow
The researchers model traffic flow as an ergodic Markov chain, where the movement of "packets" is defined by a transition matrix. The core of their strategy is the maximization of the entropy rate ($s$). In information theory, entropy represents uncertainty; in a network context, a high entropy rate indicates that packets are diffusing through the system with maximum "randomness." This randomness prevents the formation of rigid, deterministic bottlenecks, effectively acting as a proxy for network fluidity.
By calculating a "priority" for each node—based on how a small capacity increase would boost the overall entropy rate—the authors derive an optimal allocation strategy. Crucially, this calculation only requires local data: the frequency of packet arrivals and their immediate destinations.
Challenging the Hub Fallacy
A common intuition in network engineering is to prioritize "hubs" — nodes with the highest number of connections (degree). However, this research uncovers what might be called the "Hub Fallacy."
As shown in Figure 2, the maximum entropy method identifies critical nodes that degree-biased strategies often overlook. By spreading the capacity budget across a more diverse set of nodes rather than just the most connected ones, the system achieves greater overall stability and delays the onset of congestion.
Experimental Results and Performance
The method was tested across four standard synthetic network models: Cayley Trees, Regular Networks, Random Networks (Erdős–Rényi), and Scale-Free Networks (Barabási–Albert).
Across all models, the maximum entropy approach resulted in significantly higher average packet speeds ($\langle V \rangle$) compared to random or degree-biased allocation. Furthermore, the parameter $\eta$, which tracks the accumulation of "stuck" packets, remained consistently lower, indicating that the network could handle much higher loads before reaching a critical phase transition into total gridlock.
Conclusion
By shifting the focus from connectivity to entropy, this research provides a powerful, low-cost framework for mitigating congestion. The ability to achieve global network improvements using only local, observable data makes this method highly applicable to the rapidly evolving transportation and communication infrastructures of modern society. Future work will look toward validating these findings with real-world GPS and internet traffic datasets.
Summary updated