# Threshold for the Outbreak of Cascading Failures in Degree-Degree Uncorrelated Networks

Authors: Junbiao Liu; Xinyu Jin; Lurong Jiang; Yongxiang Xia; Bo Ouyang; Fang Dong; Yicong Lang; Wenping Zhang
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

In complex networks, the size of the giant component formed by unfailed nodes is critically important for estimating the robustness of networks against cascading failures. In order to explore the critical moment of cascading failures break-out, we provide a cascade of overload failure model with local load sharing mechanism and then deduce the threshold of node capacity when the large-scale cascading failures happen and unfailed nodes in steady state cannot connect to each other to form a large connected subnetwork. We get the theoretical derivation of this threshold in degree-degree uncorrelated networks and validate the effectiveness of this method in simulation. This threshold provides us with a guidance to improve the network robustness under the premise of limited capacity resource when creating a network and assigning load. Therefore, this threshold is useful and important to analyze the robustness of networks. We believe that our research provides us with a guidance to improve the network robustness under the premise of limited capacity resource.


---

## Body

## 1. Introduction

Cascading failures are a sort of phenomena in which a random failure or intentional attack on one or a few nodes leads to serve chain reaction in the networks, which can cause collapse of a large fraction of nodes in the network. It is widely found in many real-world networks, such as power transmission [1, 2], communication [3], economic [4], and biological [5] networks. A real example of cascading failures is the well-known Northeast Blackout in 2003 [6]. In this case, the outage of a generator led to a serve chain reaction of power blackout, which affected approximately 50 million people in North America and caused financial losses of about $6 billion.In order to understand the essential mechanism of cascading failures, a number of cascading models have been proposed, such as betweenness-based model [7–10], sand-pile model [11, 12], and fiber-bundle model [13, 14]. In these models, a node fails when its load exceeds its capacity. The failure of this node leads to the redistribution of load in network and can cause collapse of a large fraction of the network. Therefore, the cascading failure process of these models is highly dependent on the relation between load and capacity.When the dynamical process of cascading failures terminates in steady state, the network breaks into several connected subnetworks formed by unfailed nodes. The size of the largest connected subnetwork (i.e., the giant component) can be used to measure the severity of cascading failures, which is critically important for estimating the robustness of networks [15, 16]. It is intuitive that when the capacity increases (or the load decreases), the size of cascading failures in network reduces, which is confirmed by all of those cascading failure models above. In fiber-bundle and sand-pile model, with the capacity under a critical value (or load above a critical value), the giant component disappears, or above this critical value the size of the giant component dramatically rises up [13, 17].This critical value is a very important feature to measure the robustness of networks. However, to our knowledge, there is little research on quantitative analysis of the relation between node capacity and this threshold for the break-out of cascading failures at present.In this paper, we provide a cascade of overload failure model with local load sharing mechanism and then explore the threshold of node capacity when the large-scale cascading failures happen and there does not exist a large connected subnetwork formed by unfailed nodes.


## 2. Model

Here we provide a cascade of overload failure model with local load sharing mechanism. In this model, the statuses of nodes are divided into two categories: theunfailed andfailed. We assume that all nodes in networks are unfailed at the beginning. A node fails if its load exceeds its capacity (i.e., overload). When a node fails to work, this node is considered as transferring a fixed positive load Δ to each of its unfailed neighbors and being separated from the giant component [18–20]. When the cascading failures terminate, only those nodes in the giant component are supposed to work. It is natural to assume that the capacity C
v of a node v is proportional to its initial load L
v [21, 22] as(1)
C
v
=
1
+
α
L
v
,where the constant α is the tolerance parameter. The initial load of each node is randomly distributed following a uniform distribution on the interval [
L
m
i
n
,
L
m
a
x
]. For simplicity, we set the lower bound of initial load L
m
i
n
=
0 and the lower bound of initial load L
m
a
x
=
1 [18, 19]. Then, for arbitrary node v, the cumulative distribution function φ
(
l
) of L
v is defined as(2)
P
L
v
<
l
≜
φ
l
=
0
l
≤
0
l
0
<
l
≤
1
1
l
>
1
.The numerical process of cascading failures with local load sharing mechanism is summarized as follows.(
1) Initialization. Generate a degree-degree uncorrelated network with N nodes. Assume all nodes are unfailed. The load of each node is uniformly distributed in [
L
m
i
n
,
L
m
a
x
], where we let L
m
i
n
=
0 and L
m
a
x
=
1. The capacities of nodes are determined by (1).(
2) Beginning. Choose very few nodes randomly in the network, and set them as failed.(
3) Load Redistribution. In each round, each node which is failed in the last round transfers a fixed positive load Δ to each of its unfailed neighbors. An unfailed node turns out to be failed if it overloads in this round.(
4) Halt. Repeat step (3) if there exist overloaded nodes in the network; otherwise, the process halts. Finally, only the unfailed nodes in the giant component are supposed to work.


## 3. Analysis

### 3.1. Description of Critical Conditions

When the cascading failure process ends, the unfailed nodes in the network form several connected subnetworks. The fraction of giant component, which is the relative size of the largest connected subnetwork, can be used as a measure of the network performance against cascading failures. Figure1 shows the fraction G of the giant component as a function of tolerance parameter α in Erdös-Rényi (ER) random networks [23] and Barabási-Albert (BA) scale-free networks [24]. For each G with different average degree 〈
k
〉, there exists a critical tolerance parameter α
c, with α under which the giant component disappears and over which G increases dramatically and approaches 1 finally. When α
<
α
c, G approximately equals 0, which indicates that large-scale cascading failures occur and network breaks into extremely small clusters. There are two conditions to ensure that G approximately equals 0 when α
<
α
c:(I)
Large-scale cascading failures occur in the network; that is, the failed nodes connect to each other to form a large connected subnetwork.
(II)
When the dynamical process of cascading failures terminates in steady state, there does not exist a large connected subnetwork formed by unfailed nodes.Figure 1
The fractionG of giant component changes with increase of tolerance parameter α in ER random and BA scale-free networks.
(a)
ER random networks
(b)
BA scale-free networksIn the rest of this section, we give a theoretical derivation ofα
c with these two conditions above.


### 3.2. Large-Scale Cascading Failures Occur in the Network

First, let us consider condition (I) that large-scale cascading failures occur in the network. This condition equals the situation that the failed nodes connect to each other to form a large connected subnetwork. On average, each node fails and causes more than one of its neighbors to fail when large-scale cascading failures happen. Consider a nodev of degree k
v and any of its neighbors w. The probability that node v fails and causes node w to fail is(3)
P
L
w
+
Δ
>
1
+
α
L
w
=
P
L
w
<
Δ
α
=
φ
Δ
α
,where L
w is the initial load of node w.The cascading failures of nodes are a sort of site percolation process. Because of the locally tree-like approximation in percolation of degree-degree uncorrelated networks, the probability that nodev fails and causes m of its k
v
-
1 neighbors (subtract the node which causes node v to fail) to fail is(4)
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
.Thus, on average, the nodev fails and causes its(5)
∑
m
=
1
k
v
-
1
m
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
∑
m
=
1
k
v
-
1
m
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
∑
m
=
1
k
v
-
1
k
v
-
1
k
v
-
2
m
-
1
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
k
v
-
1
φ
Δ
αneighbors to fail.Denotep
k as the probability that a randomly picked node has degree k. According to (5), the failure of arbitrary node in the network causes its ∑
k
=
0
∞
‍
p
k
k
-
1
φ
Δ
/
α
=
〈
k
〉
-
1
φ
Δ
/
α neighbors to fail. When large-scale cascading failures occur in the network, the failure of arbitrary node causes more than one of its neighbors to fail; that is,(6)
k
-
1
φ
Δ
α
≥
1
.Thus, for condition (I) that large-scale cascading failures occur in the network, we have(7)
α
≤
k
-
1
Δ
.It is worth noting that there is not any specific assumption on degree distribution for the result above.


### 3.3. There Does Not Exist a Large Connected Subnetwork Formed by Unfailed Nodes

According to the local load sharing mechanism in our model, there may exist some nodes that do not propagate cascading failures. These nodes never fail with large tolerance parameterα, or their failure will not affect other nodes as all of their neighbors are already failed nodes. We call these nodesabsorbing nodes. Before handling condition (II), we pay close attention to these absorbing nodes. Let us consider the situation that a node v of degree k
v does not fail after k
v
-
1 of its neighbors fail and share loads (
k
v
-
1
)
Δ with it. Consequently, no matter whether node v fails or not, it can not affect other nodes any more. In this situation, node v has the ability to absorb the loads of all its neighbors by itself; thus we call this node theindependent absorbing node. The capacity and initial load of an independent absorbing node v meet the following relation: (8)
L
v
+
k
v
-
1
Δ
<
1
+
α
L
v
.But this is not the only reason that a node happens to be an absorbing node. There is another situation for a node to be an absorbing node whose load does not satisfy (8). In this situation, considering a node v, m of its neighbors are absorbing nodes; thus we only need n
v
>
k
v
-
m
-
1 to make node v an absorbing node. We call this kind of nodesdependent absorbing nodes because their ability to absorb loads depends on the other absorbing nodes of their neighbors. Dependent absorbing nodes can also prevent cascading failures locally.Figure2 gives two examples of absorbing nodes. In Figure 2(a), unfailed node 1 has five neighbors and four of them (nodes 2, 3, 4, and 5) are failed nodes. Assume that if node 6 does not fail in the following procedure of cascading failure, then node 1 does not fail either. Or in another case assume that node 6 fails and transfers a fixed value of load Δ to node 1. In the latter case, no matter whether node 1 fails or not, it can not affect any other node. Thus, node 1 is an independent absorbing node. In Figure 2(b), we assume that node 7 is not an independent absorbing node. It happens to fail if more than two of its four neighbors fail and transfer loads to it. Assume node 8 is an absorbing node; thus it never fails. Consequently, no matter whether node 7 fails or not, it can not share load with any unfailed neighbor. Therefore, node 7 in Figure 2(b) comes to be a dependent absorbing node because its ability to absorb loads depends on the absorbing node 8.Figure 2
Two examples of the absorbing nodes. In the procedure of cascading failures, an unfailed node (∘) may turn to be a failed node (•) when it overloads or does not fail as it is an absorbing node (⊚).
(a)
The independent absorbing nodes
(b)
The dependent absorbing nodesThen we consider condition (II) that there does not exist a large connected subnetwork formed by unfailed nodes. We have explained that absorbing nodes survive and keep to be unfailed after cascading failures. With increase ofα, each node has higher probability to be assigned with more capacity and be an absorbing node on average. If there exist a large number of absorbing nodes, they may connect to each other to form a large connected subnetwork which makes G greater than 0. We have divided absorbing nodes into independent absorbing nodes and dependent absorbing nodes. Furthermore, we call an absorbing node an m
-absorbing node (m
=
0,1
,
2
,
…
,
k), if and only if m of its neighbors are absorbing nodes. We assume that independent absorbing nodes are not equivalent to 0-absorbing node. For an interdependent node, if it has m absorbing nodes of its neighbors, we still treat this node as an m-absorbing node.Then, we let the probability that a node of degreek happens to be an absorbing node be a
k. The probability that node v happens to be an m-absorbing node is a
k
(
m
). Then we have(9)
a
k
=
∑
m
=
0
k
a
k
m
.In a degree-degree uncorrelated network, consider a nodev of degree k and any of its neighbors w. The probability of node w with degree j is j
p
j
/
∑
i
‍
i
p
i
=
j
p
j
/
〈
k
〉. Node w happens to be an absorbing node with the probability a
j. Then, the probability of node v’s arbitrary neighbor being an absorbing node is(10)
σ
a
=
∑
j
j
p
j
a
j
k
.According to (10), the probability that exactly m of node v’s neighbors are absorbing nodes is(11)
k
m
σ
a
m
1
-
σ
a
k
-
m
.Nodev is an m-absorbing node if it stays unfailed with k
-
m
-
1 neighbors fail and transfer loads to it. Therefore, the probability is that node v comes to be an m-absorbing node with probability(12)
a
k
m
=
k
m
σ
a
m
1
-
σ
a
k
-
m
P
L
v
+
k
-
m
-
1
Δ
<
1
+
α
L
v
=
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
φ
k
-
m
-
1
Δ
α
.We substitute (12) into (9) and get the probability that node v (i.e., arbitrary node of degree k) happens to be an absorbing node as(13)
a
k
=
σ
a
k
+
∑
m
=
0
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
φ
k
-
m
-
1
Δ
α
=
σ
a
k
+
∑
m
=
0
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
i
f
k
≤
α
Δ
+
1
σ
a
k
+
∑
m
=
k
-
1
-
α
/
Δ
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
e
l
s
e
w
h
e
r
e
=
1
-
k
-
1
Δ
α
+
k
σ
a
Δ
α
-
σ
a
k
Δ
α
i
f
k
≤
α
Δ
+
1
σ
a
k
+
∑
m
=
k
-
1
-
α
/
Δ
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
e
l
s
e
w
h
e
r
e
.According to thecascade condition [25, 26], the absorbing nodes can not connect to each other to form a large connected subnetwork with the following condition:(14)
1
k
∑
k
=
0
∞
k
k
-
1
p
k
a
k
<
1
,where p
k is probability that a randomly picked node has degree k and a
k is the probability that a node with degree k happens to be an absorbing node.Now we complete the derivation by (7), (10), (13), and (14). These four equations depend on each other. We can get the threshold of tolerance parameter α
c with the following iteration process:(1)
Assign〈
k
〉
-
1
Δ as an initial value to tolerance parameter α according to (7).
(2)
Geta
k via (10) and (13) with the current value of tolerance parameter α.
(3)
Substitutea
k into (14). If the inequality of (14) is invalid, discount a very small value from α, and then repeat step (
2
); otherwise, let α
c
=
α and finish the iteration process.


## 3.1. Description of Critical Conditions

When the cascading failure process ends, the unfailed nodes in the network form several connected subnetworks. The fraction of giant component, which is the relative size of the largest connected subnetwork, can be used as a measure of the network performance against cascading failures. Figure1 shows the fraction G of the giant component as a function of tolerance parameter α in Erdös-Rényi (ER) random networks [23] and Barabási-Albert (BA) scale-free networks [24]. For each G with different average degree 〈
k
〉, there exists a critical tolerance parameter α
c, with α under which the giant component disappears and over which G increases dramatically and approaches 1 finally. When α
<
α
c, G approximately equals 0, which indicates that large-scale cascading failures occur and network breaks into extremely small clusters. There are two conditions to ensure that G approximately equals 0 when α
<
α
c:(I)
Large-scale cascading failures occur in the network; that is, the failed nodes connect to each other to form a large connected subnetwork.
(II)
When the dynamical process of cascading failures terminates in steady state, there does not exist a large connected subnetwork formed by unfailed nodes.Figure 1
The fractionG of giant component changes with increase of tolerance parameter α in ER random and BA scale-free networks.
(a)
ER random networks
(b)
BA scale-free networksIn the rest of this section, we give a theoretical derivation ofα
c with these two conditions above.


## 3.2. Large-Scale Cascading Failures Occur in the Network

First, let us consider condition (I) that large-scale cascading failures occur in the network. This condition equals the situation that the failed nodes connect to each other to form a large connected subnetwork. On average, each node fails and causes more than one of its neighbors to fail when large-scale cascading failures happen. Consider a nodev of degree k
v and any of its neighbors w. The probability that node v fails and causes node w to fail is(3)
P
L
w
+
Δ
>
1
+
α
L
w
=
P
L
w
<
Δ
α
=
φ
Δ
α
,where L
w is the initial load of node w.The cascading failures of nodes are a sort of site percolation process. Because of the locally tree-like approximation in percolation of degree-degree uncorrelated networks, the probability that nodev fails and causes m of its k
v
-
1 neighbors (subtract the node which causes node v to fail) to fail is(4)
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
.Thus, on average, the nodev fails and causes its(5)
∑
m
=
1
k
v
-
1
m
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
∑
m
=
1
k
v
-
1
m
k
v
-
1
m
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
∑
m
=
1
k
v
-
1
k
v
-
1
k
v
-
2
m
-
1
φ
Δ
α
m
1
-
φ
Δ
α
k
v
-
1
-
m
=
k
v
-
1
φ
Δ
αneighbors to fail.Denotep
k as the probability that a randomly picked node has degree k. According to (5), the failure of arbitrary node in the network causes its ∑
k
=
0
∞
‍
p
k
k
-
1
φ
Δ
/
α
=
〈
k
〉
-
1
φ
Δ
/
α neighbors to fail. When large-scale cascading failures occur in the network, the failure of arbitrary node causes more than one of its neighbors to fail; that is,(6)
k
-
1
φ
Δ
α
≥
1
.Thus, for condition (I) that large-scale cascading failures occur in the network, we have(7)
α
≤
k
-
1
Δ
.It is worth noting that there is not any specific assumption on degree distribution for the result above.


## 3.3. There Does Not Exist a Large Connected Subnetwork Formed by Unfailed Nodes

According to the local load sharing mechanism in our model, there may exist some nodes that do not propagate cascading failures. These nodes never fail with large tolerance parameterα, or their failure will not affect other nodes as all of their neighbors are already failed nodes. We call these nodesabsorbing nodes. Before handling condition (II), we pay close attention to these absorbing nodes. Let us consider the situation that a node v of degree k
v does not fail after k
v
-
1 of its neighbors fail and share loads (
k
v
-
1
)
Δ with it. Consequently, no matter whether node v fails or not, it can not affect other nodes any more. In this situation, node v has the ability to absorb the loads of all its neighbors by itself; thus we call this node theindependent absorbing node. The capacity and initial load of an independent absorbing node v meet the following relation: (8)
L
v
+
k
v
-
1
Δ
<
1
+
α
L
v
.But this is not the only reason that a node happens to be an absorbing node. There is another situation for a node to be an absorbing node whose load does not satisfy (8). In this situation, considering a node v, m of its neighbors are absorbing nodes; thus we only need n
v
>
k
v
-
m
-
1 to make node v an absorbing node. We call this kind of nodesdependent absorbing nodes because their ability to absorb loads depends on the other absorbing nodes of their neighbors. Dependent absorbing nodes can also prevent cascading failures locally.Figure2 gives two examples of absorbing nodes. In Figure 2(a), unfailed node 1 has five neighbors and four of them (nodes 2, 3, 4, and 5) are failed nodes. Assume that if node 6 does not fail in the following procedure of cascading failure, then node 1 does not fail either. Or in another case assume that node 6 fails and transfers a fixed value of load Δ to node 1. In the latter case, no matter whether node 1 fails or not, it can not affect any other node. Thus, node 1 is an independent absorbing node. In Figure 2(b), we assume that node 7 is not an independent absorbing node. It happens to fail if more than two of its four neighbors fail and transfer loads to it. Assume node 8 is an absorbing node; thus it never fails. Consequently, no matter whether node 7 fails or not, it can not share load with any unfailed neighbor. Therefore, node 7 in Figure 2(b) comes to be a dependent absorbing node because its ability to absorb loads depends on the absorbing node 8.Figure 2
Two examples of the absorbing nodes. In the procedure of cascading failures, an unfailed node (∘) may turn to be a failed node (•) when it overloads or does not fail as it is an absorbing node (⊚).
(a)
The independent absorbing nodes
(b)
The dependent absorbing nodesThen we consider condition (II) that there does not exist a large connected subnetwork formed by unfailed nodes. We have explained that absorbing nodes survive and keep to be unfailed after cascading failures. With increase ofα, each node has higher probability to be assigned with more capacity and be an absorbing node on average. If there exist a large number of absorbing nodes, they may connect to each other to form a large connected subnetwork which makes G greater than 0. We have divided absorbing nodes into independent absorbing nodes and dependent absorbing nodes. Furthermore, we call an absorbing node an m
-absorbing node (m
=
0,1
,
2
,
…
,
k), if and only if m of its neighbors are absorbing nodes. We assume that independent absorbing nodes are not equivalent to 0-absorbing node. For an interdependent node, if it has m absorbing nodes of its neighbors, we still treat this node as an m-absorbing node.Then, we let the probability that a node of degreek happens to be an absorbing node be a
k. The probability that node v happens to be an m-absorbing node is a
k
(
m
). Then we have(9)
a
k
=
∑
m
=
0
k
a
k
m
.In a degree-degree uncorrelated network, consider a nodev of degree k and any of its neighbors w. The probability of node w with degree j is j
p
j
/
∑
i
‍
i
p
i
=
j
p
j
/
〈
k
〉. Node w happens to be an absorbing node with the probability a
j. Then, the probability of node v’s arbitrary neighbor being an absorbing node is(10)
σ
a
=
∑
j
j
p
j
a
j
k
.According to (10), the probability that exactly m of node v’s neighbors are absorbing nodes is(11)
k
m
σ
a
m
1
-
σ
a
k
-
m
.Nodev is an m-absorbing node if it stays unfailed with k
-
m
-
1 neighbors fail and transfer loads to it. Therefore, the probability is that node v comes to be an m-absorbing node with probability(12)
a
k
m
=
k
m
σ
a
m
1
-
σ
a
k
-
m
P
L
v
+
k
-
m
-
1
Δ
<
1
+
α
L
v
=
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
φ
k
-
m
-
1
Δ
α
.We substitute (12) into (9) and get the probability that node v (i.e., arbitrary node of degree k) happens to be an absorbing node as(13)
a
k
=
σ
a
k
+
∑
m
=
0
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
φ
k
-
m
-
1
Δ
α
=
σ
a
k
+
∑
m
=
0
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
i
f
k
≤
α
Δ
+
1
σ
a
k
+
∑
m
=
k
-
1
-
α
/
Δ
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
e
l
s
e
w
h
e
r
e
=
1
-
k
-
1
Δ
α
+
k
σ
a
Δ
α
-
σ
a
k
Δ
α
i
f
k
≤
α
Δ
+
1
σ
a
k
+
∑
m
=
k
-
1
-
α
/
Δ
k
-
1
k
m
σ
a
m
1
-
σ
a
k
-
m
1
-
k
-
m
-
1
Δ
α
e
l
s
e
w
h
e
r
e
.According to thecascade condition [25, 26], the absorbing nodes can not connect to each other to form a large connected subnetwork with the following condition:(14)
1
k
∑
k
=
0
∞
k
k
-
1
p
k
a
k
<
1
,where p
k is probability that a randomly picked node has degree k and a
k is the probability that a node with degree k happens to be an absorbing node.Now we complete the derivation by (7), (10), (13), and (14). These four equations depend on each other. We can get the threshold of tolerance parameter α
c with the following iteration process:(1)
Assign〈
k
〉
-
1
Δ as an initial value to tolerance parameter α according to (7).
(2)
Geta
k via (10) and (13) with the current value of tolerance parameter α.
(3)
Substitutea
k into (14). If the inequality of (14) is invalid, discount a very small value from α, and then repeat step (
2
); otherwise, let α
c
=
α and finish the iteration process.


## 4. Simulation

We validate the analytical prediction of thresholdα
c in ER random and BA scale-free networks with N
=
5000 nodes and varied average degree 〈
k
〉
=
8,10,12. The load of each node is uniformly distributed on the interval [
0,1
]. We randomly set very few nodes to fail as the beginning of the dynamical procedure. When a node fails, it transfers a fixed load Δ
=
0.01 to each of its unfailed neighbors. Figures 3 and 4 present the giant component G with different α, and the threshold α
c for G rises from zero to nonzero. Note that different values of Δ only change the scale of abscissa. For each subfigure in Figures 3 and 4, each of 50 independent simulation results is drawn, respectively. The theoretical threshold α
c is marked by the solid triangle. α
c is exactly at the moment when G rises from zero to nonzero. Therefore, our theoretical predictions are in good agreement with the simulation results. It also can be seen in both ER and BA networks that, with higher value of average degree 〈
k
〉, the value of threshold α
c increases and the networks turn out to be robuster against cascading failure. This appearance is consistent with previous studies on cascading failure.Figure 3
Validation of the analytical predictions of thresholdα
c where the giant component G exists in ER random networks. With increase of tolerance parameter α, we draw each simulated G of 50 realizations, respectively. The threshold α
c is marked by solid triangle (▲).
(a)
k
=
8
(b)
k
=
10
(c)
〈
k
〉
=
12Figure 4
Validation of the analytical predictions of thresholdα
c where the giant component G exists in BA scale-free networks. With increase of tolerance parameter α, we draw each simulated G of 50 realizations, respectively. The threshold α
c is marked by solid triangle (▲).
(a)
k
=
8
(b)
k
=
10
(c)
〈
k
〉
=
12


## 5. Conclusion

In this paper, we provide a cascade of overload failure model with local load sharing mechanism and then explore the thresholdα
c of tolerance parameter for capacity, when the giant component G formed by unfailed nodes rises from zero to nonzero. We provide two conditions to ensure that G approximately equals zero when α
<
α
c, which are as follows: (I) the large-scale cascading failures occur; (II) unfailed nodes in steady state cannot connect to each other to form a large connected subnetwork. With these two conditions, we get the theoretical derivation of α
c in degree-degree uncorrelated networks and validate the effectiveness of this theoretical derivation in simulations. We believe that when creating a network and assigning load with local load sharing mechanism, threshold α
c provides us with a guidance to improve the network robustness under the premise of limited capacity resource, especially for telecommunication networks and power grid networks.



---

*Source: 752893-2015-12-22.xml*