A High Robustness and Low Cost Model for Cascading Failures
epl draft
A High Robustness and Low Cost Model for Cascading Failures
Bing Wang and Beom Jun Kim
Department of Physics, BK21 Physics Research Division, and Institute of Basic Science, Sungkyunkwan University,
Suwon 440-746, Korea
PACS 89.75.Hc – Networks and genealogical trees
PACS 05.10.-a – Computational methods in statistical physics and nonlinear dynamics
PACS 89.20.Hh – World Wide Web, Internet
PACS 89.75.Fb – Structures and organization in complex systems
Abstract. - We study numerically the cascading failure problem by using artificially created
scale-free networks and the real network structure of the power grid. The capacity for a vertex
is assigned as a monotonically increasing function of the load (or the betweenness centrality).
Through the use of a simple functional form with two free parameters, revealed is that it is indeed
possible to make networks more robust while spending less cost. We suggest that our method to
prevent cascade by protecting less vertices is particularly important for the design of more robust
real-world networks to cascading failures.
The network robustness has been one of the most central
topics in the complex network research [1]. In scale-free
networks, the existence of hub vertices with high degrees
has been shown to yield fragility to intentional attacks,
while at the same time the network becomes robust to
random failures due to the heterogeneous degree distribu-
tion [2–5]. On the other hand, for the description of dy-
namic processes on top of networks, it has been suggested
that the information flow across the network is one of the
key issues, which can be captured well by the betweenness
centrality or the load [6].
Cascading failures can happen in many infrastructure
networks, including the electrical power grid, Internet,
road systems, and so on. At each vertex of the power
grid, the electric power is either produced or transferred
to other vertices, and it is possible that from some reasons
a vertex is overloaded beyond the given capacity, which is
the maximum electric power the vertex can handle. The
breakdown of the heavily loaded single vertex will cause
the redistribution of loads over the remaining vertices,
which can trigger breakdowns of newly overloaded ver-
tices. This process will go on until all the loads of the
remaining vertices are below their capacities. For some
real networks, the breakdown of a single vertex is suffi-
cient to collapse the entire system, which is exactly what
happened on August 14, 2003 when an initial minor distur-
bance in Ohio triggered the largest blackout in the history
of United States in which millions of people suffered with-
out electricity for as long as 15 hours [7]. A number of as-
pects of cascading failures in complex networks have been
discussed in the literature [8–16], including the model for
describing cascade phenomena [8], the control and defense
strategy against cascading failures [9, 10], the analytical
calculation of capacity parameter [11], and the modelling
of the real-world data [12]. In a recent paper [16], the cas-
cade process in scale-free networks with community struc-
ture has been investigated, and it has been found that
a smaller modularity is easier to trigger cascade, which
implies the importance of the modularity and community
structure in cascading failures.
In the research of the cascading failures, the following
two issues are closely related to each other and of signif-
icant interests: One is how to improve the network ro-
bustness to cascading failures, and the other particularly
important issue is how to design manmade networks with
a less cost. In most circumstances, a high robustness and a
low cost are difficult to achieve simultaneously. For exam-
ple, while a network with more edges are more robust to
failures, in practice, the number of edges is often limited
by the cost to construct them. In brevity, it costs much to
build a robust network. Very recently, Schäfer et. al. pro-
posed a new proactive measure to increase the robustness
of heterogeneous loaded networks to cascades. By defin-
ing the load dependent weights, the network turns to be
more homogeneous and the total load is decreased, which
means the investment cost is also reduced [15]. In the
present Letter, for simplicity, we try to find a possible way
of protecting networks based on the flow along shortest-
http://arxiv.org/abs/0704.0345v1
B. Wang B.J. Kim
l/lmax
This work
ML model in Ref.[8]
Fig. 1: The capacity c is assigned as c = λ(l)l with the initial
load l. The step function λ(l) = 1 + αΘ(l/lmax − β) with two
free parameters α and β is used in our model. For comparison,
the curve for the Motter-Lai (ML) capacity model in Ref. [8],
where λ(l) = constant, is also shown.
hop path, first proposed by Motter-Lai [8]. Through the
use of our improved capacity model, we numerically exam-
ine the cascades in scale-free networks and the electrical
power grid network. Since for heterogeneously loaded net-
works, overload avalanches can be triggered by the failure
of only one of the most loaded vertices, the following re-
sults are all based on the removal of one vertex with the
highest load. Our results suggest that networks can indeed
be made more robust while spending less cost.
We first construct the Barabási-Albert (BA) scale-free
network [17] of the size N = 5000 with the average degree
〈k〉 ≈ 4 to study the cascading failures. The BA network is
characterized by the degree distribution p(k) ∼ k−γ with
the degree exponent γ = 3, and it has been shown that the
load distribution also exhibits the power-law behavior [6],
which means that there exist a few vertices with very large
loads.
The betweenness centrality for each vertex, defined as
the total number of shortest paths passing through it, is
used as the measure of the load and computed by using
the efficient algorithm [18]. The capacity cv for the vertex
v is assigned as
cv = λ(lv)lv, (1)
where lv is the initial load without failed vertices. Al-
though it should be possible to find, via a kind of the
variational approach, the optimal functional form of λ(lv)
which gives rise to the lower cost and the higher robust-
ness (see below for the definitions of the two) we in this
work simplify λ(lv) as shown in Fig. 1:
λ(lv) = 1 + αΘ(lv/lmax − β), (2)
where Θ(x) = 0(1) for x < 0(> 0) is the Heaviside step
function, lmax = maxv lv, and we use α ∈ [0,∞) and β ∈
[0, 1] as two control parameters in the model. In Ref. [8]
a constant λ has been used (see Fig. 1 for comparison),
which corresponds to the limiting case of β = 0 with the
identification λ = 1 + α in our model.
At the initial time t = 0, the vertex with the highest
load is removed from the network, and then new loads
for all other vertices are recomputed.1 We then check the
failure condition cv < lv(t) for each vertex, and remove
all overloaded vertices to get the network at t + 1. The
above process continues until all existing vertices fulfill the
condition cv > lv(t), and the size of the giant component
N ′ at the final stage is measured. The relative size of the
cascading failures is conveniently captured by the ratio [8]
, (3)
which we call the robustness from now on. For networks
of homogeneous load distributions, the cascade does not
happen and g ≈ 1 has been observed [8]. Also for net-
works of scale-free load distributions, one can have g ≈ 1
if randomly chosen vertices, instead of vertices with high
loads, are destroyed at the initial stage [8].
In general, one can split, at least conceptually, the to-
tal cost for the networks into two different types: On the
one hand, there should be the initial construction cost to
build a network structure, which may include e.g., the cost
for the power transmission lines in power grids, and the
cost proportional to the length of road in road networks.
Another type of the cost is required to make the given
network functioning, which can be an increasing function
of the amount of flow and can be named as the running
cost. For example, we need to spend more to have big-
ger memory sizes and faster network card and so on for
the computer server which delivers more data packets. In
the present Letter, we assume that the network structure
is given, (accordingly the construction cost is fixed), and
focus only on the running cost which should be spent in
addition to the initial construction cost.
Without consideration of the cost to protect vertices,
the cascading failure can be made never to happen by
assigning extremely high values to capacities. However,
in practice, the capacity is severely limited by cost. We
expect the cost to protect the vertex v should be an in-
creasing function of cv, and for convenience define the cost
λ(lv)− 1
/N. (4)
It is to be noted that for a given value of α, the original
Motter-Lai (ML) capacity model in Ref. [8] has always a
higher value of the cost than our model (see Fig. 1). Al-
though e = 0 at β = 1, it should not be interpreted as
a costfree situation; we have defined e only as a relative
measure in comparison to the case of λ(l) = 1 for all ver-
tices. For a given network structure, the key quantities
to be measured are g(α, β) and e(α, β), and we aim to in-
crease g and decrease e, which will eventually provide us
1In real situations of failures, the initial breakdown can happen
at any vertex in the network. However, the eventual scale of dam-
ages must be greater when a heavily loaded vertex is broken, and
accordingly we in this work restrict ourselves to the worst case when
the vertex with the highest load is initially broken.
A High Robustness and Low Cost Model for Cascading Failures
 0.002  0.003  0.004
α =1.00
 =0.30
 =0.25
 =0.20
 =0.15
 =0.10
 0.002  0.003  0.004
(b) α =0.30
 =0.25
 =0.20
 =0.15
 =0.10
 0  0.2  0.4  0.6  0.8  1
α =0.30
 =0.25
 =0.20
 =0.15
 =0.10
Fig. 2: Cascading failures in the BA network of the size N =
5000 and the average degree 〈k〉 ≈ 4, triggered by the removal
of a single vertex with the highest load. The robustness g
and the cost e in Eqs. (3) and (4) are shown in (a) and (b),
respectively, as functions of β at various α values [see Fig. 1 for
α and β, the two parameters in the function λ(l) in Eq. (2)].
(c) The relation between e and g at different α’s. Compared
with the ML model in Ref. [8], it is clearly shown that the
network can be made more robust but with less cost.
a way to achieve the high robustness and the low cost at
the same time.
In Fig. 2(a), we report the robustness g for the BA net-
work of the size N = 5000 with the average degree 〈k〉 ≈ 4
as a function of β at α = 0.10, 0.15, 0.20, 0.25, 0.30, and
1.0 (from bottom to top). As β increases further beyond
the region in Fig. 2(a), the robustness g is found to de-
crease toward zero (not shown here), which is as expected
since the larger β makes vertices with larger loads less pro-
tected (see Fig. 1). We also skip in Fig. 2 small values of
β below approximately 0.001: If β < lmin/lmax, with the
minimum load lmin, all vertices are given λ(l) = 1 + α,
equivalent to the ML model corresponding to β = 0. It
is shown in Fig. 2(a) that for α . 0.30, g first increases
and then decreases as β is increased, exhibiting a well-
developed maximum gmax at β = β
∗. This is a partic-
ularly interesting observation since the network becomes
more robust (larger g) by protecting less vertices (larger
β). In more detail, the curve for α = 0.20 in Fig. 2(a)
shows the maximum gmax ≈ 0.62 (at β
∗ ≈ 0.00133), which
is about 3.5 times bigger than g ≈ 0.175 (at β = 0). In
other words, the network can be made much more robust
by assigning smaller capacities to vertices with less loads.
For larger values of α, on the other hand, it is found that
gmax occurs at β = 0, which indicates that the above find-
ing, i.e., possibility of making network more robust by
protecting less vertices, does not hold, as exemplified by
the curve for α = 1 in Fig. 2(a).
The above observation is closely related with Ref. [9],
where it has been found that in order to reduce the size
of cascades (or to have a larger g), some of less loaded
vertices should be removed just after the initial attack. In
reality, however, we believe that the direct application of
this strategy of intentional breakdowns is not easy, for cas-
cading failures usually propagate across the whole network
very soon just after the initial breakdown. In contrast, we
propose in this work a way to make the network better
prepared to breakdowns, by protecting less vertices.
In order to look at the cost benefit of protecting less
vertices in a more careful way, we plot in Fig. 2(b) the
cost e in Eq. (4) versus β at various values of α. As is
expected from Fig. 1, the cost e is shown to be a mono-
tonically decreasing (increasing) function of β (α) at fixed
α (β). Take again the case with α = 0.20 as an exam-
ple with e(β∗) ≈ 0.153 and e(β = 0) = 0.2: It is then
concluded that for α = 0.2 one can make the network
3.5 (≈ 0.62/0.175) times more robust while spending only
76.5% (≈ 0.153/0.2) of the original cost.
In Fig. 2(c), we use the same data as in Fig. 2(a) and
(b), and show the relation between the robustness and
the cost for α = 0.10, · · · , 0.30 from bottom to top. For
comparison, the values (g,e) for β = 0, corresponding to
the ML model, are also displayed as symbols at the end
of curves. It is clearly shown that for a given α, one can
achieve the higher robustness and the lower cost by tuning
β toward the right-most point on each curve. We can also
use Fig. 2(c) to choose the most efficient way to get a
given robustness g: For example, suppose that g = 0.6
is the required robustness. The vertical line for g = 0.6
crosses several different curves, and one can choose the
crossing point which has the lowest cost.
We next study the cascading failures in the real net-
work structure of the North American power grid of the
size N = 4941 [19]. Although the electrical power grid
network is a very homogeneous network in terms of the
degree distribution, the load distribution, in a sharp con-
trast, shows a strong heterogeneity as shown in Fig. 3. In
other words, the degree distribution is more like an ex-
ponential one, while the load distribution is similar to the
power-law form. The broad load distribution can be one of
the reasons of the fragility of the power grid to cascading
failures [8].
We then apply, the same method as we used above, to
the power grid, and obtain g and e as functions of β for
B. Wang B.J. Kim
104 105 106
0 5 10 15 20
Fig. 3: The cumulative load distribution of power grid network
P (l) in log-log scale. The inset shows the cumulative degree
distribution P (k) of the power grid in linear-log scale.
 0  0.01  0.02  0.03  0.04  0.05
α =1.0
 =0.8
 =0.4
 =0.2
 =0.1
 0  0.01  0.02  0.03  0.04  0.05
α =1.0
 =0.8
 =0.4
 =0.2
 =0.1
 0  0.2  0.4  0.6  0.8
α =1.0
 =0.8
 =0.4
 =0.2
 =0.1
Fig. 4: Cascading failures in the electrical power grid of the size
N = 4941. (Compare with Fig. 2 for the corresponding plots
for the BA network.) The robustness g and the cost e versus
β at various α values are shown in (a) and (b), respectively,
while (c) is for the relation between e and g. Again, it is
shown that one can achieve the higher robustness and the less
cost simultaneously, by choosing the right-most point in (c).
0.001 0.002 0.003 0.004
=0.0   
  =0.2   
  =0.4   
  =0.6   
  =0.8   
  =1.0   
Fig. 5: Cascading failures in the BA network of the size N =
5000 and the average degree 〈k〉 ≈ 4, triggered by the removal
of a single vertex with the highest load. Each vertex’s capacity
is disturbed with probability ε for α = 0.2. The data are
averaged over 20 runs.
given values of α. Figure 4 for the cascading failures of
the power grid is in parallel to Fig. 2 for the BA network:
Fig. 4(a) for g versus β, (b) for e versus β, and (c) for e
versus g. There are some quantitative differences between
curves for the power grid and the BA network. However,
qualitatively speaking, both networks are shown to ex-
hibit the following common features: (i) For a given α,
the robustness has a maximum gmax at β = β
∗, (ii) e is a
monotonically decreasing function of β at a given α, and
(iii) there exists a lob-like structure in the g-e plane, which
indicates that one can make the network exhibit a higher
robustness and a lower cost at the same time than the cor-
responding values for the ML model. It is worth mention-
ing that the power grid in Fig. 4 can be made to show the
higher g and the lower e than the ML model in a broader
region of α: Even at α = 1, the power grid can have much
better robustness and much less cost in comparison to the
ML model. Specifically, at α = 1.0 the ML model has
g ≈ 0.40 and e = 1.0 while our model can yield g ≈ 0.73
and e ≈ 0.26 (at β ≈ 0.00583) [see Fig. 4(c)], which occurs
when only 26% of vertices are given the higher capacity
λ(l) = 2, and the other remaining 74% of vertices have
the lower capacity λ(l) = 1. In other words, by assigning
lower capacities to 74% of vertices, the network becomes
much more robust.
In reality, it is also interesting to observe the effect of
noise on the dynamical process. In Ref. [20], when noise
is introduced into the nonlinear dynamical system, it has
been shown that noise changes the singularity at a special
time to a statistical time distribution and shows various in-
teresting behaviors. In the present work, we are interested
in how the presence of noise influences the final cascading
failure behavior within our scheme. Here, we introduce
A High Robustness and Low Cost Model for Cascading Failures
effects of noise as an erroneous assignment of the capac-
ity function. In detail, at a given error probability ε, the
vertex v is assigned the capacity c′v instead of its correct
c′v = cv(1 + r), (5)
where r is the uniform random variable with zero mean
(r ∈ [−1, 1]). We believe that this erroneous behavior
is plausible in reality, since the perfect knowledge for the
true value of the load for each vertex may not be available,
which may cause an erroneous assignment of the capacity
on a vertex. In the limiting case of ε = 0, we recover our
error-free results presented above. In Fig. 5, we report the
results at α = 0.2 for the robustness g for the BA network
as a function of β for different error probability ε [see
Fig.2(a) for comparison]. It is seen that for small ε, the
overall behavior is qualitatively the same as in Fig. 2(a),
i.e., the existence of a well-developed robustness peak and
gradual decrease as β is increased. The peak height of the
robustness is found to decrease as ε is increased, indicating
the negative effect of the noise. An interesting observation
in Fig. 5 is that as ε becomes larger there exits a region
of β in which the robustness is actually higher than the
error-free case of ε = 0.
In summary, we have suggested a new capacity model to
cascading failures, by improving the existing ML capacity
model in Ref. [8]. The main idea in our model is the same
as in existing studies: In a highly heterogeneous network
with a broad load distribution, vertices with large loads
should be more protected by assigning large capacities.
Different from other studies in which the capacity is as-
signed in proportion to the load, i.e., c = λl, we generalize
the model so that the proportionality constant λ is now
changed to an increasing function λ(l) of l. In more detail,
we use the Heaviside step function for λ(l) characterized
by two parameters, the step height α, and the step posi-
tion β. By applying this capacity model to the artificial
BA network as well as the real network of the power grid,
we have clearly shown that it is indeed possible to make
the network more robust, while at the same time the cost
to assign capacities is drastically reduced. We believe that
our suggested model to assign capacities to vertices should
be practically useful in designing infrastructure networks
in an economic point of view. As a final remark, it needs
to be pointed out that the model proposed in this work
should be considered as only the first step to find the op-
timal functional form λ(l) of the capacity as a function of
the load. As a future work, we are planning to apply a
sort of variational method to find the optimal functional
form of λ(l).
B.J.K. was supported by grant No. R01-2005-000-
10199-0 from the Basic Research Program of the Korea
Science and Engineering Foundation.
REFERENCES
[1] Pastor-Satorras R. and Vespignani A., Evolution and
Structure of the Internet: A Statistical Physics Ap-
proach (Cambridge University Press, Cambridge, Eng-
land, 2004); Albert R. and Barabási A.-L., Rev. Mod.
Phys., 74 (2002) 47; Dorogovtsev S.N. and Mendes
J.F.F., Adv. Phys., 51 (2002) 1079; Newman M.E.J.,
SIAM Rev., 45 (2003) 167.
[2] Albert R., Jeong H. and Barabási A.-L., Nature, 406
(2000) 378.
[3] Cohen R., Erez K., ben-Avraham D. and Havlin S.,
Phys. Rev. Lett., 85, (2000) 4626; ibid. 86 (2001) 3682.
[4] Holme P., Kim B.J., Yoon C.N. and Han S.K., Phys.
Rev. E, 65 (2002) 056109.
[5] Wang B., Tang H.W., Guo C.H. and Xiu Z.L., Physica
A, 363, (2006) 591; Wang B., Tang H.W., Guo C.H.,
Xiu Z.L. and Zhou T., ibid. 368 (2006) 607.
[6] Goh K.I., Kahng B. and Kim D., Phys. Rev. Lett., 87
(2001) 278701.
[7] U.S.-Canada Power System Outage Task Force, Final
Report on the August 14th blackout in the United States
and Canada: Causes and Recommendations (United
States Department of Energy and National Resources
Canada, April 2004.)
[8] Motter A.E. and Lai Y.C., Phys. Rev. E, 66 (2002)
065102(R).
[9] Motter A.E., Phys. Rev. Lett., 93 (2004) 098701.
[10] Hayashi Y. and Miyazaki T., cond-mat/0503615.
[11] Zhao L., Park K. and Lai Y.C., Phys. Rev. E, 70, (2004)
035101(R); Zhao L., Park K., Lai Y.C. and Ye N., ibid.
72 (2005) 025104.
[12] Kinney R., Crucitti P., Albert R. and Latora V., Eur.
Phys. J. B, 46 (2005) 101.
[13] Crucitti P., Latora V. and Marchiori M., Phys. Rev. E,
69 (2004) 045104(R).
[14] Holme P. and Kim B.J., Phys. Rev. E, 65 (2002) 066109.
[15] Schäfer M., Scholz J. and Greiner M., Phys. Rev. Lett.,
96 (2006) 108701.
[16] Wu J. J, Gao Z.Y. and Sun H. J., Phys. Rev. E, 74,
(2006) 066111.
[17] Barabási A.-L. and Albert R., Science, 286 (1999) 509.
[18] Newman M.E.J., Phys. Rev. E, 64, (2001) 016132; Pro.
Natl. Acad. Sci., U.S.A. 98 (2001) 404.
[19] Watts D.J. and Strogatz S.H., Nature, 393 (1998) 440.
[20] Fogedby H. C., Poutkaradze V., Phys. Rev. E, 66,
(2002) 021103.
http://arxiv.org/abs/cond-mat/0503615
