where y
i
st
is the number of shortest paths between nodes s and t that run through node i, and θ
st
denotes the total number of available shortest paths from s to t. The capacity of a node is the
maximum load that the node can handle. Following Refs. [17, 18], the capacity of node i is
assigned as
C
i
¼ð1 þ a
i
ÞL
0
i
ð2Þ
Where L
0
i
is the initial load and α
i
(α
i
0) is the tolerance parameter.
The cascading failure is triggered by removing the highest-load node in the network result-
ing in the globally redistribution of the flow and node loads [17, 18]. If a surviving node is over-
loaded, i.e. L
i
> C
i
, then it fails, leading to further load redistribution. This process continues
recursively until no more nodes overload. Moreover, it is assumed that only the nodes in the
giant component remain functional.
Optimal model of capacity allocation
Methods of resource allocation are generally framed to reduce the vulnerability (enhance the
robustness) of networks against cascading failures with a limited cost. The variables to be opti-
mized are defined as the tolerance parameter vector a
!
(i.e. a
!
¼½a
1
; a
2
; ...; a
N
0, is a vector
of network size N). Motter-Lai (ML) model [17] is the most basic and widely used model, in
which α
i
are the same values c(c > 0) for all nodes. Wang et al. [18] proposed a model in which
a
i
¼ cYð
L
i
L
max
bÞ, wher e Θ(x) = 0(1) for x < 0(x > 0), is a two-valued function. The latter
model performs better than the former one, so it is possible that a pattern of a
!
that yields lower
vulnerability and cost can be found by means of a variation approach.
The vulnerability of a network is defined as
Vða
!
Þ¼
N
0
ða
!
Þ
N
ð3Þ
where N
0
ða
!
Þ is the number of failed vertices under the tolerance vector a
!
and N is the total
number of vertices in the network. Obviously, the smaller V is, the more robust the network
will be. The cost of whole netwo rk resources is defined, in accordance with previous works
[18], as
Eða
!
Þ¼
1
N
X
N
i¼1
a
i
¼
1
N
a
!
1
!
ð4Þ
where 1
!
is a column vector of ones. The larger the E is, the more resources the network costs.
The cascade-robustness network is a network with redundant vertex capacity. However,
redundancy usually means extra cost. Robustness and cost are expected to be in opposition,
requiring trade-offs. Therefore, we define the overall objective function Fða
!
Þ of a network by
aggregating vulnerability and cost through an adjusting parameter ω(0 < ω 1) balancing the
importance of vulnerability and cost:
Fða
!
Þ¼oVða
!
Þþð1 oÞEða
!
Þð5Þ
When ω is small, we pay more attention to controlling the cost rather than reducing the vul-
nerability. On the contrary, when ω is large, we focus more on enhancing the network robust-
ness and care less about the cost. It is easily found that the smaller the objective function is, the
better the results are.
Maximum cost is always a constraint in real world projects, which are subject to a budget.
Thus, it is necessary to set whole network maximum cost as a constraint. Since ML model is
Optimal Allocation of Node Capacity in Cascade-Robustness Networks
PLOS ONE | DOI:10.1371/journal.pone.0141360 October 23, 2015 3/12