Source-linked AI summary
Congestion induced by the structure of multiplex networks
Albert Solé-Ribalta, Sergio Gómez, Alex Arenas
TL;DR
Congestion can emerge in multiplex transportation even when the individual layers would remain uncongested. The paper derives analytical onset conditions and approximations, and finds that shortest-path imbalances between layers can induce congestion, with the expressions assessed against simulations.
Problem
Transportation flows in multiplex networks can congest, but the role of their interconnected structure in producing congestion beyond that of individual layers needs to be quantified.
Source: INTRODUCTION · p. 1Method
The paper models queue dynamics on multiplex networks and derives a critical injection rate using node processing limits and multiplex betweenness.
Source: INTRODUCTION · p. 2Results
The analytical expressions accurately predict congestion onset and show that multiplex structure can induce congestion through unbalanced shortest-path traffic between layers.
Source: INTRODUCTION · pp. 2–3Takeaways & Limitations
Shortest-path routing can concentrate load on the more efficient layer and lead to congestion that does not occur when the layers operate separately.
Source: INTRODUCTION · p. 1The analysis covers congestion onset only; after congestion begins, cascading queues make the ingoing-rate expression inapplicable.
Source: INTRODUCTION · p. 2
Abstract
from arXiv · showhide
Multiplex networks are representations of multilayer interconnected complex networks where the nodes are the same at every layer. They turn out to be good abstractions of the intricate connectivity of multimodal transportation networks, among other types of complex systems. One of the most important critical phenomena arising in such networks is the emergence of congestion in transportation flows. Here we prove analytically that the structure of multiplex networks can induce congestion for flows that otherwise will be decongested if the individual layers were not interconnected. We provide explicit equations for the onset of congestion and approximations that allow to compute this onset from individual descriptors of the individual layers. The observed cooperative phenomenon reminds the Braess' paradox in which adding extra capacity to a network when the moving entities selfishly choose their route can in some cases reduce overall performance. Similarly, in the multiplex structure, the efficiency in transportation can unbalance the transportation loads resulting in unexpected congestion.
INTRODUCTION
The paper models transportation in multiplex networks and derives analytical conditions for congestion onset. It finds that shortest-path traffic can become unbalanced across layers, inducing congestion that the individual layers would not reach alone.
INTRODUCTION
- The model tracks queue growth through injected, incoming, and processed elements, and defines onset when a node reaches its maximum processing rate.The critical injection rate is determined by the maximum interconnected betweenness across nodes and layers.Source: INTRODUCTION · p. 2
- The analysis addresses congestion onset, not the already congested regime, where cascading queues invalidate the ingoing-rate expression.The derivation assumes a common injection rate and equal maximum processing rates across nodes; the paper says these assumptions simplify but are not crucial to the analysis.Source: INTRODUCTION · p. 2
- Because most shortest paths stay within a layer in the studied Erdős–Rényi networks, the onset approximation rescales individual-layer betweenness by shortest-path migration between layers.The approximation is especially accurate when the fraction of paths fully contained within layers is near 1; it can be less reliable at low mean degrees.Source: INTRODUCTION · pp. 3–4
- Identical layers split equivalent shortest paths, halving each layer’s betweenness, whereas a more efficient layer can capture nearly all shortest paths.For the example with path lengths 2 and 3, the shorter-path layer has approximately all the shortest paths (µ1 ≈ 1, µ2 ≈ 0).Source: INTRODUCTION · p. 3
- Multiplex structure induces congestion when it reaches onset at a lower injection rate than either layer operating individually.The flow shifts toward the more efficient layer, which can become overloaded.Source: INTRODUCTION · pp. 1, 3, 4
- The analytical expressions show close agreement with simulations on Erdős–Rényi and random geometric multiplexes, including accurate prediction of congestion-inducing regions.The conclusion reports perfect agreement with empirical results; the approximation for the critical injection rate is also described as highly accurate.Source: INTRODUCTION · pp. 3–4