Dynamic Effects Increasing Network Vulnerability to Cascading Failures
Dynamic Effects Increasing Network Vulnerability to Cascading Failures
Ingve Simonsen,1, 2, ∗ Lubos Buzna,1, 3 Karsten Peters,1 Stefan Bornholdt,4 and Dirk Helbing1
1Dresden University of Technology, Andreas-Schubert-Straße 23, D-01086 Dresden, GERMANY
2Department of Physics, Norwegian University of Science and Technology (NTNU), NO-7491 Trondheim, NORWAY
3University of Zilina, Univerzitna 8215/5, SK-01026 Zilina, SLOVAKIA
4Institute for Theoretical Physics, University of Bremen, Otto Hahn Allee 1, D-28334 Bremen, GERMANY
(Dated: June 10, 2021)
We study cascading failures in networks using a dynamical flow model based on simple conserva-
tion and distribution laws to investigate the impact of transient dynamics caused by the rebalancing
of loads after an initial network failure (triggering event). It is found that considering the flow dy-
namics may imply reduced network robustness compared to previous static overload failure models.
This is due to the transient oscillations or overshooting in the loads, when the flow dynamics adjusts
to the new (remaining) network structure. We obtain upper and lower limits to network robustness,
and it is shown that two time scales τ and τ0, defined by the network dynamics, are important
to consider prior to accurately addressing network robustness or vulnerability. The robustness of
networks showing cascading failures is generally determined by a complex interplay between the
network topology and flow dynamics, where the ratio χ = τ/τ0 determines the relative role of the
two of them.
PACS numbers: 89.75.-k; 89.20.-a; 75.40.Gb; 89.65.-s
Societies rely on the stable operation and high perfor-
mance of complex infrastructure networks, which are crit-
ical for their optimal functioning. Examples are electri-
cal power grids, telecommunication networks, water, gas
and oil distribution pipelines, or road, railway and airline
transportation networks. Their failure can have serious
economic and social consequences, as various large-scale
blackouts and other incidents all over the world have
recently shown. It is therefore a key question how to
better protect such critical systems against failures and
random or deliberate attacks [1, 2, 3]. Issues of net-
work robustness and vulnerability have not only been
addressed by engineers [4, 5], but also by the physics
community [2, 3, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17].
In the initial studies of this kind [2, 6, 7, 8, 11], the pri-
mary concern was dedicated to what can be termed struc-
tural robustness; the study of different classes of network
topologies and how they were affected by the removal of
a finite number of links and/or nodes (e.g. how the av-
erage network diameter changed). It was concluded that
the more heterogeneous a network is in terms of, e.g.,
degree distribution, the more robust it is to random fail-
ures, while, at the same time, it appears more vulnerable
to deliberate attacks on highly connected nodes [7, 11].
Later on, the concepts of network loads, capacities, and
overload failures were introduced [9, 10, 12, 14, 15, 16].
For networks supporting the flow of a physical quantity,
the removal of a node/link will cause the flow to redis-
tribute with the risk that some other nodes/links may be
overloaded and failure prone. Hence a triggering event
can cause a whole sequence of failures due to overload,
and may even threaten the global stability of the net-
work. Such behavior has been termed cascading fail-
ures. A seminal work in this respect is the paper by
Motter and Lai [9]. These authors defined the load of
a node by its betweenness centrality [3, 9]. Subsequent
studies introduced alternative measures for the network
loads [12] as well as more realistic redistribution mecha-
nisms [12, 14, 15, 16].
In all studies cited above, the redistribution of loads
is treated time-independent or static. We will refer to
them collectively as static overload failure models. The
load redistributions in such models are instantaneously
and discontinuously switched to the stationary loads of
the new (perturbed) network, i.e. the transient dynam-
ical adjustment towards the new stationary loads of the
perturbed network is neglected.
The aim of this Letter is to compare robustness es-
timates of complex networks against cascading failures
where the dynamical flow properties are taken into ac-
count relative to those where they are not (static case).
This work does not intend to target a specific system
(or network); instead we aim at being as generic as pos-
sible in the choice of dynamical model with the conse-
quence that particular details and features of a specific
system have to be neglected, i.e. we work with a minimal
model as often favored in physics. Nevertheless, the con-
ceptually simple dynamical phenomenological flow model
that we propose, incorporates flow conservation, network
topology, as well as load redistribution features that are
shared by real-life systems. On this background, it is
expected (cf. Fig. 1) that the model results will reflect
some important properties of real-life systems.
For matters of illustration and to facilitate compari-
son with previous results [9, 10, 12, 14, 15, 16], we have
worked with topologies of power transmission networks.
Although our model seems to capture stylized features of
electrical networks (see Fig. 1), we stress that our goal is
not a realistic representation of those, nor is our model re-
stricted to such systems. Within the proposed model, we
http://arxiv.org/abs/0704.1952v2
0 10 20 30 40
time [s]
0 10 20 30 40 50
time [s]
0 10 20 30 40
time [steps]
0 10 20 30 40 50
time [steps]
(a) (b)
(c) (d)
FIG. 1: (Color online) Comparison of the time-dependent
link loads after an triggering event (taking place at t = 0) as
predicted by state-of-the-art power simulators (Figs. 1(a) [18]
and (b) [19]), and the simple “flow-conserving” model de-
scribed and used in the present work (Figs. 1(c) and (d)).
want to demonstrate that time-dependent adjustments
can play a crucial role. In particularly, we will show that
static overload failure models give the lower limit of the
vulnerability of flow networks to failures and attacks, and
hence of the probability of cascading failures.
In order to study this, in the very tradition of physics,
we use a simple flow model with few parameters, which
however considers the network topology, flow conserva-
tion, and the distribution of loads over the neighboring
links of a node [20, 22]. We assume a network consist-
ing of N nodes and represent it by a matrix W , whose
entries Wij ≥ 0 (with i, j = 1, 2, . . . ,N ) shall reflect
the weight of the (directed) link from node j to i (with
Wij = 0 indicating no link present). The relative weights
Tij = Wij/wi shall define the elements of the transfer ma-
trix T , where wj =
i=1 Wij is the total outgoing weight
of node j [22]. These elements describe the distribution
of the overall flow (per unit weight) cj(t) reaching node
j at time t over the neighboring links i. When the flow
is assumed to reach the neighboring nodes i at time step
t+1, we obtain ci(t+1) =
j=1 Tijcj(t)+j
i [20, 22, 23],
where we have added possible source terms (j±i > 0) or
sink terms (j±i < 0). In vectorial notation, the network
flow equation reads
c(t+ 1) = Tc(t) + j± , (1)
resembling Kirchhoff’s first law from circuit theory.
If j± = 0, the stationary solution to Eq. (1) is a con-
stant vector with components c
i (∞) ∼ 1/
N , while
with a source term present (j± 6= 0), it can be expressed
as c(∞) = c(0)(∞) + (1− T )+ j± with (1− T )+ denot-
ing the so-called generalized inverse [24] of the singu-
lar matrix 1 − T . Hence, the total directed current on
link j → i at time t becomes Cij(t) = Wijcj(t), from
which also the (undirected) load Lij(t) of this link can
be defined via Lij(t) = Cij(t) + Cji(t) [28]. Closed-
form expressions for the flow dynamics at single nodes
have been derived in Ref. [23]. These allow one to study
the wave-like spreading and dissipation of perturbations
in the network while propagating via neighboring links,
second-next, etc. (see Fig. 2). Such perturbations may
result from the redistribution of flows after the failure of
an overloaded link.
In the seminal work of Motter and Lai [9], failure of a
node was based on the long-term overload, i.e. a node
was assumed to fail whenever the stationary load in the
perturbed network (considering previously broken nodes)
exceeded the node capacity. The (node) capacities were
defined as 1 + α times the (stationary) loads of the orig-
inal network with α ≥ 0 being a global tolerance factor
(i.e. a relative excess capacity or safety margin). In other
words, the evaluation of overloading was previously done
after the system relaxed, without considering the time-
history of how it got to this state (static overload failure
models) [9, 10, 12, 14, 15, 16].
In this Letter, we generalize this approach towards a
dynamical overload failure model. Specifically, in our
computer simulations we assumed a link from node j
to i to be overloaded (and to fail) whenever the time-
dependent load Lij(t) exceeded the link capacity Cij for
at least a time period τ , the overload exposure time. The
link capacities were defined analogously to Motter and
Lai [9] as
Cij = (1 + α)Lij , (2)
where Lij denote the stationary loads of the original net-
work.
In the following, we study the transient dynamical ef-
fects and overload situations that may occur before the
stationary state is reached. While for τ = 0, a failure
results immediately after a first-time overload, τ > 0
implies that the system will have to be overloaded for a
certain time period in order to cause a failure. The static
overload failure model corresponds to τ → ∞, or in prac-
tice, τ ≫ τ0, where τ0 denotes the transient time of the
system (the inverse of the smallest non-zero eigenvalue of
T ). Therefore, the ratio χ = τ/τ0 can be used to inter-
polate between the static (χ → ∞) and (instantaneous)
dynamical overload failure (χ = 0) models. While the
static overload failure model describes the upper limit of
network robustness (the best case), the dynamic overload
failure model with τ = 0 gives the lower limit (the worst
case) due to an overshooting flow dynamics (Fig. 2). Re-
alistic cases are expected to lie between these two limiting
cases, corresponding to a finite value of χ.
Apart from network robustness to overload failures,
the value of χ also determines the dynamics of failure
cascades. In the dynamic case with χ = 0, close-by links
are more likely to be overloaded and to fail than in the
static case (χ → ∞). Therefore, in the dynamic scenario
0 200 400 600 800 1000
time [steps]
0.980
0.990
1.000
1.010
1.020
1.030
Link A
Link B
0 20 40 60 80 100
time [steps]
Link A
0 200 400 600 800 1000
time [steps]
1.000
1.005
1.010
1.015
Link C
Link D
Link E
0 10 20 30 40 50 60
time [steps]
Link F
FIG. 2: (Color online) (a) Illustration of the dynamics of
our network flow model assuming the topology of the UK
high-voltage power transmission grid (300–400 kV) consist-
ing of 120 geographically correctly placed nodes (generators,
utilities, and transmission stations) and 165 links (transmis-
sion lines). The network was treated as unweighted and
undirected. In our simulations, twenty of the existing net-
work nodes were chosen randomly to play the role of gener-
ator (source) and utility (sink) nodes (
˛n±i /N
˛ = 2.5 · 10−4),
ten of each kind. In Fig. 2(a) the location of these nodes
are indicated by filled red squares and filled green diamonds
respectively. At time t = 0, before which the network loads
were in the stationary state (Lij(t < 0)), the network was
perturbed by removing a transmission line in Scotland (the
red dashed link marked by 0 in Fig.2(a)). The resulting nor-
malized transient link loads, Lij(t)/Lij(t < 0), are depicted
in Figs. 2(b) and (c) for some selected links of the UK trans-
mission grid, as indicated in Fig. 2(a). The horizontal dash-
dotted lines correspond to the normalized stationary loads of
the links.
one tends to have a pronounced “failure wave” sweeping
over the network.
In order to further illustrate the difference between the
static and dynamic cascading failure models, as well as
getting a quantitative measure of the level of overesti-
mation of robustness, we investigate one of the networks
already studied by Motter and Lai [9] — the Northwest-
ern American power transmission network obtained from
Ref. [26] (see also Refs. [11, 27]). To evaluate the effect of
an initial network perturbation and the following cascade
(if any), we study the fraction of nodes and links, GN (α)
and GL(α), respectively, remaining in the giant compo-
nent of the network after potential cascading failures have
ceased, which have been initiated by the random failure
of a link [9]. Both quantities behave similarly [29]. They
are displayed in Fig. 3 for the US power transmission net-
work as functions of the tolerance parameter α. It has
been checked and found that our static overload failure
model well reproduces the general behavior previously
reported in Ref. [9]. Namely, global cascading failure
will occur under random attacks (or failures) mainly for
heterogeneous networks.
According to Fig. 3, there is a pronounced difference
between the static and (instantaneous) dynamic overload
failure model, corresponding to upper and lower esti-
mates to the network robustness. As is shown in the
inset to Fig. 3, it can be as significant as 80%, and for
more homogeneous link weights we have found differences
even higher than 95%. Only for quite significant toler-
ance factors (α ≥ 50%), the discrepancy between the
two estimates becomes insignificant. Moreover, it has
also been found that the static model tends to be more
sensitive to the location of sources (and sinks). Thus,
our results show that the role of the dynamical process
taking place on the network can be important when esti-
mating the robustness of networks to failures and random
attacks. It is not only the topology of the network that
matters, but also the properties of the network dynamics
as measured by χ = τ/τ0. The change in one or both of
them will require a new robustness estimate.
In conclusion, we have simulated a simple network
flow model considering, besides network topology, a flow-
conserving dynamics and distribution of loads. Within
this framework, we have studied the role of the tran-
sient dynamics of the redistribution of loads towards the
steady state after the failure of network links. This tran-
sient dynamics is often characterized by overshootings
and/or oscillations in the loads, which may result in char-
acteristic “failure waves” spreading over the network. We
have furthermore found that, considering only the loads
in the steady state (the static overload model), gives a
best case estimate (upper limit) of the robustness. The
worst case (lower limit) of robustness can be determined
by the instantaneous dynamic overload failure model and
may differ considerably.
Our simple dynamical approach provides additional in-
sights into systems in which network topology is com-
bined with flow, conservation and distribution laws.
These are potentially useful to understand, better de-
sign and protect critical infrastructures against failures.
For instance, overloads related to high electrical currents
cause (through over-heating of wires) a slow spreading
0 0.2 0.4 0.6 0.8
Static
Dynamic  (τ = 0)
Dynamic  (τ = 1)
Dynamic  (τ = 10)
0 0.2 0.4 0.6
FIG. 3: (Color online) The robustness of the Northwestern US
power transmission grid [26], consisting of 4941 nodes, with
an average node degree of 2.67 (cf. also Refs. [11, 15, 27]).
The average fraction of links (or nodes), G(α), remaining in
the giant component of this network (after cascading) is de-
picted as function of the tolerance parameter α, using the
static and dynamic overload failure models described in the
text. To obtain these results, the links were assigned weights,
drawn from a uniform distribution on the interval [1, 10], and
200 generator and utility nodes of strength
˛ = 10−8
were assigned randomly (100 of each type). The results were
obtained by averaging over all possible triggering events (sin-
gle link removals). The inset shows the difference, ∆G(α),
between the static and dynamic overload failure models.
of failures as compared to the adjustment dynamics of
the currents. This corresponds to χ ≫ 1. In contrast,
within the validity limits of Ohm’s law, one may also use
our model to mimic effects of overloads related to over-
voltages. In this case, we have χ ≪ 1, and link failures
reflect the anticipatory disconnection of lines to prevent
damages of the network and its components. Other ex-
amples, besides electrical power grids, are traffic systems,
where overloaded streets cause unreasonably long travel
times along links, which may be interpreted as effective
link failures. The resulting choice of alternative routes
corresponds to a rebalancing of loads and is expected to
cause transient effects, with finite values of χ.
As the model allows for effective simulations, it could
also be useful for close to real-time planning and opti-
mization of network topologies and load sharing, partic-
ularly for large networks. Fully realistic state-of-the-art
simulation tools for, say, electrical power grids that in-
clude network capacities, inductors, power generation,
etc., are computationally expensive and therefore not so
well suited for real-time simulation of large networks or
their topological optimization. Hence, simpler models
could quickly and efficiently give a useful overview that
could serve as the starting point for more detailed off-line
simulations using classical power network simulators.
The authors gratefully acknowledge the support from
the EU Integrated Project IRRIIS (027568) and ESF
COST Action P10 “Physics of Risk” and comments by
J.L. Maŕın and A. Diu.
∗ Electronic address: Ingve.Simonsen@phys.ntnu.no
[1] A. Kaufmann, D. Grouchko, and R. Cruon, Mathemat-
ical Models for the Study of the Reliability of Systems
(Academic Press, 1977).
[2] R. Albert and A.-L. Barabási, Rev. Mod. Phys. 74, 47
(2002).
[3] M. E. J. Newman, SIAM Rev. 45, 167 (2003).
[4] R. Billinton and W. Li, Reliability Assessment of Elec-
tric Power Systems Using Monte Carlo Methods (Plenum
Press, NY, 1994).
[5] Y. Dai, J. McCalley, N. Samra, and V. Vittal, IEEE T.
Power Syst. 16, 4 (2001).
[6] R. Albert, A. L. H. Jeong, and A.-L. Barabási, Nature
406, 378 (2000).
[7] D. J. Watts, Proc. Natl. Acad. Sci. USA 99, 5766 (2002).
[8] P. Holme, B. J. Kim, C. N. Yoon, and S. K. Han, Phys.
Rev. E 65, 056109 (2002).
[9] A. E. Motter and Y.-C. Lai, Phys. Rev. E 66, 065102(R)
(2002).
[10] A. E. Motter, Phys. Rev. Lett. 93, 098701 (2004).
[11] R. Albert, I. Albert, and G. L. Nakarado, Phys. Rev. E
69, 025103(R) (2004).
[12] P. Crucitti, V. Latora, and M. Marchiori, Phys. Rev. E
69, 045104(R) (2004).
[13] A. Scirè, I. Tuval, and V. M. Egúıluz, Europhys. Lett.
71, 318 (2005).
[14] L. Huang, L. Yang, and K. Yang, Phys. Rev. E 73,
036102 (2006).
[15] J. Bakke, A. Hansen, and J. Kertész, Europhys. Lett. 76,
717 (2006).
[16] L. Dall’Asta, A. Barrat, M. Barthélemy, and A. Vespig-
nani, J. Stat. Mech. P04006 (2006).
[17] P. Kaluza, M. Ipsen, M. Vingron, and A. S. Mikhailov,
Phys. Rev. E 75, 015101(R) (2007).
[18] R. Sadikovic, Ph.D. thesis, ETH Zurich, Switzerland
(2006).
[19] The EUROSTAG power simulation package
(http://wwweurostag.epfl.ch/).
[20] K. A. Eriksen, I. Simonsen, S. Maslov, and K. Sneppen,
Phys. Rev. Lett. 90, 148701 (2003).
[21] I. Simonsen, K. A. Eriksen, S. Maslov, and K. Sneppen,
Physica A 336, 167 (2003).
[22] I. Simonsen, Physica A 357, 317 (2005).
[23] D. Helbing and R. Molini, Phys. Lett. A 212, 130 (1996).
[24] A. Ben-Israel and T. Greville, Generalized Inverses
(Springer-Verlag, Berlin, 2003), 2nd ed.
[25] The UK power transmission grid data were digitized from
a map of the European transmission grid purchased from
Glückauf Verlag.
[26] D. J. Watts and S. H. Strogatz, Nature 393, 440 (1998).
[27] L. A. N. Amaral, A. Scala, M. Barthelemy, and H. E.
Stanley, Proc. Natl. Acad. Sci. USA 97, 11149 (2000).
[28] Alternatively one could have defined directed loads by
Lij(t) = Cij(t), but this possibility will not be considered
herein.
[29] This is a consequence of the network being either al-
most unaffected by an initial link removal, or experienc-
ing global failure where the whole network collapses.
mailto:Ingve.Simonsen@phys.ntnu.no
