Hidden geometry of traffic jamming

We introduce an approach based on algebraic topological methods that allow an accurate characterization of jamming in dynamical systems with queues. As a prototype system, we analyze the traffic of information packets with navigation and queuing at nodes on a network substrate in distinct dynamical regimes. A temporal sequence of traffic density fluctuations is mapped onto a mathematical graph in which each vertex denotes one dynamical state of the system. The coupling complexity between these states is revealed by classifying agglomerates of high-dimensional cliques that are intermingled at different topological levels and quantified by a set of geometrical and entropy measures. The free-flow, jamming, and congested traffic regimes result in graphs of different structure, while the largest geometrical complexity and minimum entropy mark the edge of the jamming region.

Figure 1

Bottom panel: Double-logarithmic scale of traffic load fluctuations $N_p\left(t_w\right)$ against time window $t_w$ for different driving rates $R=0.1$, 0.25, 0.3, 0.35, 0.4, 0.425, 0.5, 0.6, 0.7, and 0.8 (bottom to top). Top panel: The logarithmic growth rate $\lambda$ of the time series $(•$) plotted against $R$; the scaled maximal topological dimension $d_{\max }/125$ of a node in the corresponding TV graph computed for the range of topology levels $q$ indicated in the legend (solid symbols) and in the graphs of the randomized time series $(\times )$ plotted against $R$.

Figure 2

Illustration of the natural visibility mapping of two time series $a\left(t\right)$ and $b\left(t\right)$ exhibiting different levels of fluctuation. The number above each data point (vertical bar) indicates connections visible along the thin lines emanating from the top of the bar.

Figure 3

(a) The giant cluster of the substrate network with two hubs and different scale-free distributions for incoming and outgoing links, finite clustering coefficients and disassortative mixing characteristic for Webgraph [6]. The vertex size correlates with its degree. (b) TV graph representing the traffic density $N_p\left(t_w\right)$ time series for $R=035$. Here, vertices stand for data points while edges indicate natural visibility connections between data points. (c) Ranking distributions for the vertex degree $k_i$ in the studied TV graphs, indicated by $R$ values, against the vertex rank $r_i$. (d) Three-dimensional rendering of a closeup of the TV graph for $R=0.35$ illustrating a typical pattern of connections analyzed in this work. Varying colors from dark to pale indicate vertices of a larger degree.

Figure 4

The first, second, and third structure vectors (top to bottom panel) of the visibility graphs representing the traffic density fluctuation in three different traffic regimes (solid symbols) and the corresponding randomized time series $(+,☆,\times$). In the latter group, the connectivity at $q=2$ drops below 40% (indicated by $\to$). On the other hand, the most complex graph has 51% connectivity at the topology level $q=8$ (indicated by $\downarrow$).

Figure 5

(a) The geometrical response function $f_q$, and (b) the entropy of occupation of topology level $q,S_Q\left(q\right)$, plotted against $q$ for graphs representing time series for different rates $R$. The corresponding quantities of the graph from the randomized time series for $R=0.35$ are shown by $☆$.

Figure 6

Difference between the upper bound $f_q^{\max }$ and the actual $f_q$ value for various TV graphs related to the traffic density time series on the substrate network Webgraph (a) and a homogeneous network Statnet [6], where the jamming occurs at $R=0.8$ (b).

Figure 7

(a) Examples of time series $n_g\left(t\right)$ for $R=0.1$ (black) and $R=0.35$ [orange (gray)] line; (b) fluctuations around local trends of all time series; (c) power spectrum; and (d) the distributions of avalanche sizes for different $R$ values. The legend applies to all three panels (b)–(d). The corresponding quantities of a randomized [15] time series in (b), (c), and (d) are shown by $\times$ symbols.