# Geometry of commutes in the universality of percolating traffic flows

Sasan Ebrahimabadi1 Ali Hosseiny2<EMAIL_ADDRESS>Jingfang Fan3 Abbas
Ali Saberi4,5<EMAIL_ADDRESS>&<EMAIL_ADDRESS>1School of Computer
Science, Carleton University, Ottawa ON K1S-5B6, Canada  2Department of
Physics, Shahid Beheshti University, Evin, Tehran, 1983969411, Iran  3School
of Systems Science, Beijing Normal University, 100875 Beijing, China
4Department of Physics, University of Tehran, P. O. Box 14395-547, Tehran,
Iran  5Max Planck Institute for the Physics of Complex Systems, 01187 Dresden,
Germany

###### Abstract

Traffic congestion is a major problem in megacities which increases vehicle
emissions and degrades ambient air quality. Various models have been developed
to address the universal features of traffic jams. These models range from
micro car-following models to macro collective dynamic models. Here, we study
the macrostructure of congested traffic influenced by the complex geometry of
the commute. Our main focus is on the dynamics of traffic patterns in Paris,
and Los Angeles each with distinct urban structures. We analyze the complexity
of the giant traffic clusters based on a percolation framework during rush
hours in the mornings, evenings, and holidays. We uncover that the
universality described by several critical exponents of traffic patterns is
highly correlated with the geometry of commute and the underlying urban
structure. Our findings might have broad implications for developing a
greener, healthier, and more sustainable future city.

complexity; Universality; Traffic flows; Commute geometry

Introduction.—Studying the behavior of vehicular traffic has attracted the
attention of researchers for a long time. Excessive use of vehicles could
bring about various problems, one of which is elevating the congestion. People
are dealing with congestion almost every day, and it brings negative effects
on their lives. A thorough analysis [1] of traffic situations in $471$ urban
areas across the United States has revealed that travel delays due to traffic
congestion pushed drivers to waste more than $3$ billion gallons of fuel and
kept travelers stuck in their cars for about $7$ billion additional hours—$42$
hours per rush-hour commuter. These all translate to a total nationwide price
loss of $160$ billion during traffic congestion or $960$ per commute. In
addition, the ”2019 Urban Mobility Report” remarked that traffic delay was
equivalent to nearly $7$ full working days of motorists in $2017$. The
negative cost of this delay could cause a loss of over $1000$ dollars [2].

The other problem that emerges from congestion is the emission of pollutants
into the air. Studies on the source of fine particulate matter in different
areas in the United States indicated that motor vehicles are one of the
primary contributing factors to air pollution and consequently to global
warming [3, 4]. The stop-and-go is a common phenomenon that occurs during
congestion. Consecutive acceleration and deceleration in stop-and-go will lead
to extensive burning and consumption of fuel and consequent air pollution.
Releasing harmful fine particulates is highly related to mortality risk. Lung
cancer and cardiovascular mortality are increased as a result of high amounts
of pollutants in the air [5, 6, 7, 8, 9, 10]. These effects have led
scientists to find an optimal way to mitigate the congestion by exploring
different aspects of traffic.

Greenshields et al. were pioneers in measuring the speed, capacity, traffic
flow, and density by taking photos [11, 12, 13]. Researchers started to probe
into the behavior of traffic both from macro and micro points of view. In this
regard, different approaches were proposed to solve the problems that traffic
carries (See [14, 15] and references therein).

Totally Asymmetric Simple Exclusion Processes (TASEP), Cellular Automaton
(CA), and Car Following models are classified in the microscopic approaches in
which monitoring the occupancy of each cell is essential [15, 16, 17, 18, 19,
20, 21]. The impact of roundabouts, crossroads, sudden acceleration, and
deceleration, overtaking on multiple roads are the most frequent questions in
this approach [22, 23, 24, 25, 26, 15]. On the other hand, macroscopic models
often investigate the global impact of traffic throughout the city. One of the
most well-known macroscopic models was proposed by Ligthill-Whitham and
Richards (LWR) [15, 27, 28] where the authors have utilized a first-order
partial differential equation to explain the dynamic of traffic.

a b
c d

Figure 1: Mapping traffic pattern in Paris to percolation. a. The regular
Google map. Different colors indicate the intensity of traffic on roads. b.
The map is embedded onto a $112\times 112$ grid. In the first step, we
indicate cells in which at least one of the pixels belongs to a road. A porous
lattice appears in green cells. We will analyze the percolation of traffic on
this porous lattice. c. Cells are colored by the traffic report of Google. If
only one pixel within a cell is assigned by either orange, red, or dark red,
we then consider the whole cell as a traffic cell. d. Percolation of traffic
congestion in the porous lattice. Traffic clusters are displayed in yellow.
The red cluster indicates the giant cluster.

Propagation of congestion throughout the city and identifying the traffic zone
in the city is one of the frequent questions in macroscopic models. Daganzo
[29, 30] has introduced the cell transmission model which shows the evolution
of traffic flow over complex networks. This model can investigate and predict
the dynamics of traffic including nucleation, spanning, and the emergence of
queues due to congestion.

Percolation theory [31] is a useful tool for studying the organization of
global traffic flow on a lattice model [32, 33]. Recent studies on macroscopic
models have utilized percolation theory to disclose the propagation of traffic
in urban areas [34, 35]. In this geometric approach, locally congested roads
will form traffic clusters that gradually grow over time and eventually merge
into one giant cluster. The critical point or the percolation threshold
$p_{c}$ coincides with the emergence of the giant cluster that is of great
practical importance. The percolation problem is one of the most important
universality classes in the critical phenomena characterized by a set of
genuine critical exponents. Scaling relations ensure that all critical
exponents can be obtained from only two independent ones e.g., the fractal
dimension $D_{f}$ of the giant cluster and the Fisher exponent $\tau$
governing the cluster size distribution at criticality. Determination of the
universality class of traffic clusters can indeed provide insights into the
underlying mechanism and influential parameters that shape the propagation of
traffic jams over time [36, 32, 37].

Figure 2: Giant cluster of traffic jam in Paris. The red cluster represents
the giant cluster at the percolation critical point in Paris in the morning of
a working day. The orange cluster represents the second largest cluster.
Figure 3: Mean cluster size in Paris. The mean cluster size $\chi(p)$ as a
function of the traffic rate $p$ in the working days (a) and weekends (b) in
Paris. The vertical dashed lines show the location of maximums at the critical
traffic rate $p_{c}$.

Here, we study the structure of traffic clusters in Los Angeles and Paris by
using the concepts of percolation theory. We compare their properties in the
morning and the afternoon/evening rush hours of weekdays and weekends. The
critical question is whether the percolation properties of traffic clusters in
these cities with totally different road network structures are influenced by
the geometry of the commutes.

Results.—We first embed the Paris map into a $112\times 112$ grid in our
analysis. Snapshots are taken from Google Maps for live traffic patterns every
$5$ minute in $14$ days during June and November $2018$. Roads in Google Maps
carry four possible colors: green, orange, red, and dark red. Colorless
regions in the map are related to places other than roads, which we will not
consider in this study (Fig. 1). The green stands for a road in the traffic-
free mode. In other cases, however, traffic is involved with the increasing
intensity from orange to dark red. This setting provides a network of roads of
Paris and Los Angeles embedded in a discretized two-dimensional space (Fig.
1).

Figure 4: Giant cluster of traffic jam in weekends. The red cluster represents
the giant cluster at the percolation critical point in Paris on a weekend. The
orange cluster represents the second largest cluster.  Figure 5: Fractal
property of the giant cluster: $\log$-$\log$ plots of the average mass $M$ of
the giant cluster of a traffic pattern in a window of size $L$ in the mornings
of the working days (a), evenings of the working days (b), weekends (c) in
Paris. (d) Implementation of random percolation model on the city road
geometry. The slopes give the fractal dimension of the giant cluster at the
critical thresholds. The solid lines are the best fits to our data with
$R^{2}>0.99$. The error bars (based on standard error) are the same size as
the symbols.

Materials and Methods.—Google Maps has a feature called “Google Traffic” that
provides accurate real-time traffic information to online users. The
information is graphically coded in four different colors: green for the
traffic-free mode, orange for moderate traffic, red for high traffic, and dark
red for traffic congestion (Fig. 1). We captured the live traffic patterns of
Paris and Los Angeles in $5$ minute intervals for two weeks. There are
different features in the snapshots that we captured (e.g. names of roads,
rivers, Parks, etc.) but we only used the graphical information for the
traffic report.

In the first step, we use image processing to convert the RGB matrix (which is
a 3D matrix ) into a 2D matrix with values ranging from 1 to 4 each for colors
from green to dark red, respectively (Green=1, orange=2, red=3, and dark
red=4). We have then embedded the matrix information onto a square lattice of
size $1792\times 1792$. Since the cell size on our original lattice was less
than a typical road width, we have used a coarse-grained lattice by merging
each $16\times 16$ cell into one larger cell. Thus our initial lattice of size
$1792\times 1792$ shrank into a lattice of size $112\times 112$.

Models. we used the site-percolation model to investigate traffic propagation
and dynamics throughout Paris and Los Angeles. We consider a site (or cell) to
be congested if its attributed value is higher than $1$. This means that all
sites with colors in orange, red, and dark red are congested. We define $q=2$
as a threshold for each cell in the matrix $A_{ij}$ i.e.,

$A_{ij}=\begin{cases}1\qquad\text{if}\qquad\qquad&A_{ij}\geq q\\\
0\qquad\text{if}\qquad\qquad&A_{ij}<q\end{cases}$ (1)

Map onto a percolation problem. Fig. 1a represents a typical snapshot of the
traffic pattern in Paris. Fig. 1b shows the porous lattice of the road network
on which our percolation analysis is carried out. Fig 1c is an example of the
transformation of the original 3D RGB Google Maps traffic pattern into the
two-dimensional $112\times 112$ lattice. Each lattice cell may contain several
colored pixels in the original map. We use the max-pooling method which
assigns the darkest color of pixels to the cell. We then consider all cells
with different colors as occupied cells in percolation and represent them with
orange. The nearest neighbors of occupied sites on the lattice form a
connected cluster, and the number of occupied sites in this cluster defines
its size $s$. The giant cluster with the largest size at the given traffic
rate is shown in red in Fig 1d. The traffic rate is related to the occupation
probability $p$ that measures the ratio of the total number of occupied sites
to the total number of green sites i.e., all sites that belong to the road
network. Once $p$ reaches a critical threshold $p_{c}$ i.e., the large-scale
traffic is jammed and the giant cluster spans across the lattice.

To capture these critical points, we first measure the mean cluster size
(analogous to the susceptibility of the system), $\chi(p)$ defined by

$\chi(p)=\Sigma^{\prime}_{s}s^{2}n_{s}(p)/\Sigma^{\prime}_{s}sn_{s}(p),$ (2)

where $n_{s}(p)$ denotes the average number of clusters of size $s$ at each
traffic rate $p$, and the prime on the sums indicates the exclusion of the
largest cluster in each measurement.

Fig. 2 illustrates an example of the traffic pattern at the critical rate in
the morning of a working day in Paris. The red cluster is the largest cluster
and the orange one is the second largest cluster.

Fig. 3a represents the mean cluster size of traffic pattern in both morning
(green open circles) and evening (red solid circles) on a working day in
Paris. The divergence in $\chi(p)$ signals the critical traffic rate at the
onset of large-scale traffic congestion. Remarkably, the critical traffic rate
in the morning is smaller than the critical rate in the evening. We find that
the average traffic rate in the morning for the observed period is $0.525\pm
0.05$ and for the evening is $0.67\pm 0.02$. This means that the morning of
working days in Paris carries a lower capacity of traffic flow which can be
caused by the common and localized destinations of vehicles in the morning and
thus common roads. Fig. 3b shows the percolation of traffic flow during a
weekend in Paris. As it can be seen, the critical traffic rate $p_{c}$ in the
morning ($\sim 0.664\pm 0.02$) and evening ($\sim 0.68\pm 0.02$) is very close
to that of the evening of the working days ($\sim 0.67\pm 0.02$). In the
evenings and weekends, the destinations are chosen by the people which are
well distributed all over the city which provides more variety of routes for
vehicles and as a result the traffic load of the city increases in this period
of time. This difference is also well represented schematically in the giant
cluster of the traffic pattern for weekday morning in Fig. 2 which is a highly
porous and low-density fractal structure versus a more dense structure of the
giant cluster observed in the weekend shown in Fig. 4.

Such observations prompt us to investigate whether the difference between
weekend and weekday evening critical thresholds versus weekday morning
thresholds is indicative of fundamental differences in traffic patterns from
the perspective of critical complex systems. The universality allows to
grouping of microscopically quite different physical models and phenomena with
the same behavior near criticality into universality classes characterized by
a set of critical exponents related to the broad symmetry groups. In
percolation theory, the critical exponents, unlike the critical threshold, do
not depend on the microscopic details of the underlying lattice but only on
the Euclidean dimension $d$ and the dimensionality of the order parameter.

Figure 6: Mean cluster size in LA. The mean cluster size $\chi(p)$ as a
function of the traffic rate $p$ in the working days in LA. The vertical
dashed line shows the location of maximums at the critical traffic rate
$p_{c}$.

To evaluate the universality class of the traffic patterns at the critical
rates, we first measure the fractal dimension $D_{f}$ of the giant clusters
which also implies the emergence of self-similarity in the geometric feature
of the percolation clusters. If the giant cluster is scale invariant then it
requires that the mean mass $M$ of the cluster within the window of length $L$
would increase as a power-law with size, i.e.

$M(L)\propto L^{D_{f}}.$ (3)

The results of our fractal analysis based on examination of the scaling
relation Eq. 3 are illustrated in Fig. 5 where we have shown $\log$-$\log$
plots of the average mass of the giant cluster within a window of linear size
$L$. The slope of the linear fit to our data gives the best estimation for the
fractal dimension. We find $D_{f}=1.57\pm 0.05$ for the giant cluster of
traffic jam in the morning of the working days (Fig. 5a), while we find higher
values $1.76\pm 0.05$ (Fig. 5b) and $1.73\pm 0.05$ (Fig. 5c) for the evening
of the working days and the weekends, respectively, in agreement with our
earlier graphical observations from Figs. 2 and 4.

In order to further elucidate the nature of the universality classes observed
at different times in Paris, we examine the implementation of the random
percolation model on the geometry of the road network in Paris. To this aim,
we randomly choose a site on the roads and occupy it with a vehicle. We find
that the model shows a critical behavior at a critical rate $p_{c}=0.69\pm
0.04$ and the fractal dimension of the giant cluster is estimated to be
$D_{f}=1.78\pm 0.03$ (Fig. 5d). Remarkably, this random percolation model
agrees well with our observations of the real traffic situations in Paris
during the evenings of the working days and the weekends. This finding is in
accord with our previous justification of the random distribution of vehicle
destinations during the evening of working days and weekends.

Table 1: Percolation threshold $p_{c}$, fractal dimension $D_{f}$, and the
Fisher exponent $\tau$ for the considered cities and models.
City/Model | $p_{c}$ | $D_{f}$ | $\tau$
---|---|---|---
exponent | p-value
working day mornings in Paris | $0.525\pm 0.05$ | $1.57\pm 0.05$ | $2.33\pm 0.04$ | $0.25$
working day evenings in Paris | $0.67\pm 0.02$ | $1.76\pm 0.05$ | $2.17\pm 0.04$ | $0.70$
weekends in Paris | $0.68\pm 0.02$ | $1.73\pm 0.05$ | $2.16\pm 0.05$ | $0.21$
random percolation on Paris | $0.69\pm 0.04$ | $1.78\pm 0.03$ | $-$ | $-$
working day mornings in LA | $0.735\pm 0.05$ | $1.77\pm 0.05$ | $2.16\pm 0.04$ | $0.63$
random percolation on LA | $0.70\pm 0.04$ | $1.70\pm 0.04$ | $-$ | $-$
2D site percolation on square lattice | $0.592\pm 0.003$ | $91/48$ | $187/91$ | $-$

We have also performed a similar analysis on the statistical behavior of the
traffic pattern in the city of Los Angeles (LA). The urban structure of LA and
the road network are completely different from the city of Paris, and this
helps to better understand the effect of commute geometry on the universality
and the traffic threshold. Figure 6 shows the mean cluster size as a function
of traffic rate in the morning of LA. The global maximum in $\chi$ happens at
$p_{c}=0.735\pm 0.05$ which is close to that of the random percolation model
on Paris as well as our observations on the evenings and the weekends in
Paris. To examine its universal properties at the criticality, we have
measured an independent critical exponent i.e., the Fisher exponent $\tau$
shown in Fig. 7 using the following scaling relation at the critical threshold

$n(s)\propto s^{-\tau}.$ (4)

We use the algorithm described in [38] to evaluate the Fisher exponents. To
this aim, we first estimate the lower bound of the traffic cluster size
distribution where it begins following a power-law behavior. Thereafter, we
used maximum likelihood estimation (MLE) to find the best scaling parameter
that fits our observed data. To check the validity of our measured scaling
parameter, we used the goodness of fit test which would generate a p-value. We
measure the p-value by using the Kolmogorov–Smirnov (KS) test to calculate the
distance between the empirical data and the hypothesized power-law model.
Afterward, we create a large number of synthetic data with the given scaling
parameter and lower bound and then calculate the distance between the model
and each synthetic data set by using KS statistics. We can define the p-value
once we calculate the fraction of times that the KS result is larger than that
of real data. It is reasonable to say that a distribution follows a power-law
behavior if the p-value is greater than $\sim 0.1$ (for a detailed explanation
of the method see [38]).

Figure 7: The Fisher critical exponent $\tau$ at the percolation threshold.
(a) Working days in the morning in Paris, (b) Working days in the evening in
Paris, (c) Weekends in Paris, and (d) LA.

By employing the aforementioned method, we find the Fisher exponent $\tau\sim
2.33$ for the mornings of the working days in Paris and almost the same
exponents around $\tau\sim 2.16$ for the evenings and the weekends of Paris
and LA (Table 1). This shows the crucial role that is played by the geometry
of commutes in shaping the universal and characteristic properties of traffic
patterns in megacities. We have also carried out random percolation analysis
on the LA road network and found results close to those obtained in Paris. All
measured thresholds and exponents are summarized in Table 1. These all support
our conclusion that the commute geometry leaves its footprints on the traffic
patterns.

Conclusion.—In classical critical phenomena, the universal features are
independent of microscopic details and only dependent on the dimensionality
and the underlying symmetries. In a given support dimension, changing the
universality class requires manipulating interactions in a relevant manner. In
the percolation model that we used in the analysis of the traffic patterns of
Paris, the universality class in the mornings of working days is distinctly
different from the weekends and evenings of working days. The only important
difference in these two situations is the change in the distribution of supply
and demand at the city level, which seems to have a much more significant
effect than what was thought. Because even when we look at the dynamics of the
traffic pattern in the city of Los Angeles, with a different city structure
and geometry from Paris, the universality class is like the weekends in Paris,
which is also indistinguishable from a case where vehicles are randomly
distributed in the city. These observations are very promising because our
results suggest that without manipulating the road network and urban structure
(urban geometry) which is very costly if not impossible, the critical traffic
rate of the city can be significantly increased by changing the distribution
of supply and demand sources in the city. This means that the universality
class of the traffic model is manageable based on the random percolation
model, which seems to provide an optimal condition for city traffic.

Acknowledgement The authors thank Aaron Clauset for providing and openly
sharing the codes for calculating the exponent of power law distributions.

## References

  * [1] D. Schrank, B. Eisele, T. Lomax, J. Bak, et al., The texas a $\&$ m transportation institute and inrix 9, 10 (2015).
  * [2] D. Schrank, B. Eisele, T. Lomax, et al., https://rosap.ntl.bts.gov/view/dot/61408 (2019).
  * [3] M. J. Rizzo and P. A. Scheff, Atmospheric Environment 41, 6276 (2007).
  * [4] D. M. Hammond, J. T. Dvonch, G. J. Keeler, E. A. Parker, A. S. Kamal, J. A. Barres, F. Y. Yip, and W. Brakefield-Caldwell, Atmospheric Environment 42, 720 (2008).
  * [5] H. Yeo and A. Skabardonis, in Transportation and Traffic Theory 2009: Golden Jubilee (Springer, 2009) pp. 99–115.
  * [6] J. A. Laval and L. Leclercq, Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 368, 4519 (2010).
  * [7] F. Laden, J. Schwartz, F. E. Speizer, and D. W. Dockery, American Journal of Respiratory and Critical Care Medicine 173, 667 (2006).
  * [8] C. A. Pope III and D. W. Dockery, Journal of the air $\&$ waste management association 56, 709 (2006).
  * [9] A. C. Stern, Air Pollution: The effects of air pollution, Vol. 2 (Elsevier, 1977).
  * [10] S. Matsumoto, T. Park, and H. Kawashima, International Journal of Intelligent Transportation Systems Research 12, 1 (2014).
  * [11] D. S. Turner, 75 Years of the Fundamental Diagram for Traffic Flow Theory: Greenshields Symposium: July 8-10, 2008, Woods Hole, Massachusetts (Transportation Research Board, 2011).
  * [12] B. D. Greenshields, J. Thompson, H. Dickinson, and R. Swinton, in Highway Research Board Proceedings, Vol. 13 (1934).
  * [13] B. Greenshields, J. Bibbins, W. Channing, and H. Miller, in Highway research board proceedings, Vol. 1935 (National Research Council (USA), Highway Research Board, 1935).
  * [14] D. Helbing, A. Hennecke, V. Shvetsov, and M. Treiber, Mathematical and computer modelling 35, 517 (2002).
  * [15] D. Helbing, Reviews of modern physics 73, 1067 (2001).
  * [16] P. L. Krapivsky, S. Redner, and E. Ben-Naim, A kinetic view of statistical physics (Cambridge University Press, 2010).
  * [17] J. de Gier and B. Nienhuis, Physical Review E 59, 4899 (1999).
  * [18] P. G. Gipps, Transportation Research Part B: Methodological 15, 105 (1981).
  * [19] K. Nagel and M. Schreckenberg, Journal de physique I 2, 2221 (1992).
  * [20] H. Emmerich and E. Rank, Physica A: Statistical Mechanics and its Applications 234, 676 (1997).
  * [21] S. Maerivoet and B. De Moor, Physics reports 419, 1 (2005).
  * [22] E. Pronina and A. B. Kolomeisky, Physica A: Statistical Mechanics and its Applications 372, 12 (2006).
  * [23] T. Tang, H.-J. Huang, S. Wong, and X. Xu, Physica A: Statistical Mechanics and its Applications 376, 649 (2007).
  * [24] M. E. Foulaadvand and P. Maass, Physical Review E 94, 012304 (2016).
  * [25] M. E. Foulaadvand and M. Neek-Amal, EPL (Europhysics Letters) 80, 60002 (2007).
  * [26] R. Wang and H. J. Ruskin, Computer Physics Communications 147, 570 (2002).
  * [27] M. J. Lighthill and G. B. Whitham, Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences 229, 317 (1955).
  * [28] P. I. Richards, Operations research 4, 42 (1956).
  * [29] C. Daganzo, University of California, Berkeley (1993).
  * [30] C. F. Daganzo, Transportation Research Part B: Methodological 29, 79 (1995).
  * [31] A. A. Saberi, Physics Reports 578, 1 (2015).
  * [32] R. Cohen and S. Havlin, Complex networks: structure, robustness, and function (Cambridge University Press, 2010).
  * [33] A. Bunde and S. Havlin, Fractals and disordered systems (Springer Science $\&$ Business Media, 2012).
  * [34] D. Li, B. Fu, Y. Wang, G. Lu, Y. Berezin, H. E. Stanley, and S. Havlin, Proceedings of the National Academy of Sciences 112, 669 (2015).
  * [35] G. Zeng, D. Li, S. Guo, L. Gao, Z. Gao, H. E. Stanley, and S. Havlin, Proceedings of the National Academy of Sciences 116, 23 (2019).
  * [36] S. N. Dorogovtsev, A. V. Goltsev, and J. F. Mendes, Reviews of Modern Physics 80, 1275 (2008).
  * [37] B. Barzel and A.-L. Barabási, Nature physics 9, 673 (2013).
  * [38] A. Clauset, C.R. Shalizi and M.E. Newman, SIAM review, 51, 661 (2009).