Cite this Article
Liu Jun, Xiong Qing-Yu†, Shi Xin, Wang Kai, Shi Wei-Ren. Load-redistribution strategy based on time-varying load against cascading failure of complex network . Chinese Physics B, 24(7): 076401  
Permissions
Load-redistribution strategy based on time-varying load against cascading failure of complex network
Liu Juna), Xiong Qing-Yu†b),c), Shi Xina), Wang Kaia), Shi Wei-Rena)
School of Automation, Chongqing University, Chongqing 400044, China
Key Laboratory of Dependable Service Computing in Cyber Physical Society, Ministry of Education, China
School of Software Engineering, Chongqing University, Chongqing 400044, China

†Corresponding author. E-mail: cquxqy@163.com

*Project supported by the National Basic Research Program of China (Grant No. 2013CB328903), the Special Fund of 2011 Internet of Things Development of Ministry of Industry and Information Technology, China (Grant No. 2011BAJ03B13-2), the National Natural Science Foundation of China (Grant No. 61473050), and the Key Science and Technology Program of Chongqing, China (Grant No. cstc2012gg-yyjs40008).

Abstract

Cascading failure can cause great damage to complex networks, so it is of great significance to improve the network robustness against cascading failure. Many previous existing works on load-redistribution strategies require global information, which is not suitable for large scale networks, and some strategies based on local information assume that the load of a node is always its initial load before the network is attacked, and the load of the failure node is redistributed to its neighbors according to their initial load or initial residual capacity. This paper proposes a new load-redistribution strategy based on local information considering an ever-changing load. It redistributes the loads of the failure node to its nearest neighbors according to their current residual capacity, which makes full use of the residual capacity of the network. Experiments are conducted on two typical networks and two real networks, and the experimental results show that the new load-redistribution strategy can reduce the size of cascading failure efficiently.

PACS: 64.60.aq; 89.75.–k
Keyword: load redistribution; time-varying load; cascading failure; complex networks
1. Introduction

Complex networks are all around us, they are not strange to us, for example, traffic networks, [1, 2] power grids, [3– 6] the Internet, [7, 8] computer networks, [9] and so on; they can all be described by complex networks. With rapid economic and social development, some problems are getting more and more serious in these infrastructure networks, such as traffic congestion, blackout, and so on. Du et al.[10] introduced a shortest-remaining-path-first queuing strategy into a network traffic model, which is helpful for designing optimal networked-traffic systems. Liu et al.[11] proposed a routing strategy based on the gravitational field of the node and the routing awareness depth, which can reduce traffic jams and improve the ability of the network to resist congestion. Considering the scale-free property in real networks, Liu et al.[12] adopted the scale-free network to represent the individual interactions in the particle swarm optimization (PSO) algorithm and explored the dynamical searching process microscopically, finding that the cooperation of hub nodes and non-hub nodes play a crucial role in optimizing the convergence process. It has the implication in controlling a variety of dynamical processes taking place on complex networks. The robustness of networks is one of the central issues in complex network research. Cascading failure can cause great damage to complex networks, which can be described as follows. The loads of the network are time-varying, and the capacities of the network are limited. The failure of one node can cause the redistribution of loads, and this redistribution may make the loads of some nodes exceed their capacities, which leads to further failures and load-redistribution and finally to a cascading breakdown of the whole network. There has been a lot of research related to cascading failure. This issue is crucial for infrastructure networks, which our modern human society greatly relies on. Duan et al.[13] proposed a novel node importance indicator based on the information about cascading failures and analyzed the node importance evolution mechanism in-depth, which is helpful to improve the network robustness.

There are also many models proposed to improve network robustness against cascading failure. Motter et al.[14] assumed that the load is exchanged between every pair of nodes and transmitted along the shortest path connecting them. The load of a node is defined as the betweenness of the node. The removal of nodes in general changes the distribution of the shortest paths. They assume that the capacity of a node is proportional to its initial load, which is adopted in many researches.[15– 19] The definition of the load and the load-redistribution strategy require each node to master the whole information of the network though the global load-redistribution strategy can obtain good results. Therefore, it tends to be used in small complex networks. For large scale networks, the global information is hard to obtain. Moreover, the load may not be transmitted along the shortest path. Then, Wang et al.[20] proposed a cascading failure model based on the local preferential redistribution rule of the load of the failure node, defining the initial load of a node as the function of the degree of the node. Wang et al.[15] put forward a local weighted flow redistribution rule to investigate the cascading failure on weighted complex networks. They assumed that the additional flow received by an edge is proportional to its weight (flow). Ren et al.[21] presented a model of cascading failure, and it adopts a new redistribution strategy based on the difference between capacity and the initial load. Duan et al.[22] proposed a new cascading model based on a tunable load redistribution model. It can achieve better robustness against cascading failure than the previous model by adjusting the redistribution range and heterogeneity. Chen et al.[23] studied the influences of network coupling strength, subnetwork edge, and coupling edge of interdependent networks on the network robustness. These strategies based on the local information rather than global information are more suitable for large scale networks, but in these strategies the load of the failure node (or edge) is redistributed to its neighbors according to their initial load or initial residual capacity rather than their current load or their current residual capacity. It will lead to an unreasonable redistribution of loads, which will easily lead to further failures and eventually spread over the entire network. In fact, the loads of the real network are constantly changing, such as the traffic in a traffic network, the power consumption in a power grid, and so on. Then, the residual capacity of the node will change along with the time-varying load of the node, so it is necessary to propose a load-redistribution strategy based on local information considering the time-varying loads of a network.

In view of the above problems, we propose a new load-redistribution strategy, which is able to make full use of the residual capacity of the network. The experimental results show that it can well improve the network robustness against cascading failure, especially when the loads of the network are constantly changing.

2. Model

A new model considering a time-varying load is proposed based on the load-capacity model. There are three main elements, including the initial load of the node, the capacity of the node, and the load-redistribution strategy.

2.1. The definition of the initial load

In many researches, the initial load of the node is defined as the total number of shortest paths passing through this node. The definition can well describe the initial load of the node, but it needs the global information, and the global information is not readily available in a large-scale network. Wang et al.[24] defined the initial load of the node as the product of the degree of the node and the sum of the degree of its neighbors, which is in positive correlation with betweenness centrality.[25] Therefore, this definition can describe the initial load of the node as well as betweenness centrality. Moreover, it is based on the local information instead of the global information, so the initial load of node i is defined as

where ki is the degree of node i, Γ i is the set of neighbors of node i, α is a tunable parameter and governs the strength of the initial load, and N is the number of nodes in a complex network.

2.2. The definition of the capacity

The capacity of a node is the maximum load that the node can deal with. As is well known, the larger the node capacity is, the stronger the network robustness is. However, the capacity of a node is severely limited by the cost in real networks. Thus, Motter and Lai[14] assume that the capacity Ci of node i is proportional to its initial load , that is

where β > 0 is the tolerance parameter, and N is the number of nodes in a complex network. This definition is commonly used in many researches. In this paper, we also use this definition.

2.3. Load-redistribution strategy

The strategies based on the local information mentioned in Section 1 are all based on the fixed factors, including the initial load, capacity, and initial residual capacity. Moreover, these strategies assume that the load of a node is always its initial load no matter when the node is destroyed. The strategy based on the initial residual capacity can be described as

The strategy based on the initial load is defined as

In this paper, we assume that the capacity Ci of node i is proportional to its initial load . Substituting Eq. (2) to Eq. (3), we obtain

from which one can see that Eqs. (3) and (4) are equivalent and we call these two strategies fixed strategy (FS).

However, in real networks, the load of a node is constantly changing rather than remaining the same due to the existence of the disturbance variable. For example, in a traffic network, the traffic varies with the time of the day. Generally speaking, there is more traffic both in the morning and at dusk. If at this time one node of the traffic network fails, it will induce further failures more easily than at ordinary times and eventually lead to a cascading breakdown of the entire network. Similarly, in a power grid, the power consumption varies along with the time. Therefore, a strategy based on local information considering a time-varying load is needed to improve the robustness of the large scale networks.

In this paper, we propose a load-redistribution strategy considering the time-varying load and the time-varying residual capacity against cascading failure. Here, we call this strategy the time-varying strategy (TVS). The time-varying load Li(0) of node i is defined as

where Δ l is the disturbance variable, it can be defined according to the variation trend of the load. Here, in order to explore the robustness of the model, for simplicity, , ε i is a random number between − 1 and 1. When β > 1, the time-varying load Li(0) of node i may be less than zero. However, in real networks Li(0) ≥ 0. In fact, β ≤ 1 is enough to protect the network against cascading failure, so we do not need to worry about Li(0) < 0 in this paper.

The load of failure node i is redistributed to the nearest neighbors of node i in proportion of the current remaining capacity, as

where Cj is the capacity of node j, Lj(t) is the load of node j at the time step t, q is the number of time steps before the cascading process stops, j is the nearest neighbor of node i, and Γ i is the set of nearest neighbors of node i.

According to this principle, the extra load Δ Lji that node j should obtain from the failure node i is

so at the time step t + 1, if Lj(t) ≤ Cj, the load of node j is

where Γ j is the set of nearest neighbors of node j. If Lj(t + 1) > Cj, node j is removed from the network, and the load Lj(t + 1) of node j is redistributed to its nearest neighbors, and this load-redistribution may lead to new overload failure. This cascading process may stop after a few steps, while it could also spread over the entire network.

To discuss the cascading failure more easily, we introduce Pi to evaluate the proportion of failure nodes due to the removal of node i

where Fi is the number of failure nodes caused by the removal of node I, N is the total number of nodes in the complex network. Obviously, 0 ≤ Fi ≤ N − 1.

Then, the average proportion of failure nodes due to the removal of one node of the entire network can be described as

The lower the proportion of failure nodes is, the more robust the whole network is against cascading failure.

3. Experiments and discussion
3.1. Network data

The topology of the network plays an important role in studying the cascading failure of the network.[15, 20] Networks with different topology may show different anti-destroying abilities. In this paper, we consider two typical complex networks, including BA networks[26] and WS networks.[27] It has been found that the small-world and scale-free properties are ubiquitous in nature and human society.[28]

BA network proposed by Barabá si and Albert[26] is a scale-free network, and many real networks display a scale-free feature, so it is significant to discuss the cascading failures under scale-free networks. However, some networks are homogeneous. In order to structure these networks, we consider WS networks with a small-world property. The two typical complex networks used in this paper were both generated by Pajek. For each network, the number of nodes N = 1000 and ⟨ k⟩ = 8.

Although typical model networks are useful in understanding how real networks behave, they cannot catch many of the structural properties of real systems. Therefore, we also consider some real-life complex networks including the US power grid network (UPG)[29] and the USA airport network (UAN).[30] The UPG is the high-voltage power grid in the Western States of the United States of America. There are 4941 nodes and 6594 edges in the power grid of the western United States. The nodes are transformers, substations, and generators, and the ties are high-voltage transmission lines. The UAN is the network of the 500 busiest commercial airports in the United States. A tie exists between two airports if a flight was scheduled between them in 2002.

3.2. Experimental analysis

In this research, to compare our load-redistribution strategy (TVS) with FS on four networks, we remove only one node i initially and calculate the proportion of failure nodes Pi after the cascading failure process is over. The P is calculated according to Eq. (11) and each experimental result is the average value of 10 realizations. The experiment is divided into two parts. One is under the condition that ε i = 0, the other is under the condition that ε i is a random number between − 1 and 1.

Firstly, we assume that the loads of the nodes in complex networks are always their initial loads (ε i = 0). In this condition, we compare TVS with FS under a BA network and a WS network. Figure 1 shows the relationship between β and P under different strategies. From Fig. 1(a), one can see that in the BA network the average proportion of failure nodes due to the removal of one node is becoming lower with the increase in β . There will be no cascading failure when β ≥ β T, where β T is the critical threshold at which a phrase transition occurs from normal state to collapse. It can also be seen that the proportion of failure nodes based on TVS is lower than that based on FS for the same α when β is a constant value and β < β T. Furthermore, one can also see that in the BA network the average proportion of failure nodes P is becoming lower with the increase of α . Figure 1(b) shows the relationship between β and P under different strategies in the WS network. From Fig. 1(b), one can also see that the proportion of failure nodes based on TVS is lower than that based on FS. In addition, one can see that the results with bigger α are better than those with smaller α in the beginning, while with the increase of β the results with smaller α tend to be better than those with bigger α . It is not accidental. According to Eq. (1), the smaller the value of α is, the more homogeneous the load of the nodes is. There exists a small enough interval of β when α = 0.4, in which the network can change from normal to cascading failure of the entire network immediately. While with the increase of α , the homogeneousness of the load is becoming more and more insignificant and there are no such small intervals of β when α = 1.6, which lead to a slow decrease of P though at the beginning P with α = 1.6 is smaller than P with α = 0.4, so it is reasonable that the results of α = 0.4 are better than the results of α = 1.6 when β > 0.13.

Fig. 1. The relationship between β and P under different strategies in two typical networks (ε i = 0): (a) BA network, (b) WS network.

To further illustrate the effectiveness of TVS, we remove the node with the highest load of four networks (two typical networks and two real networks) and calculate the proportion of failure nodes Pmax. The results are shown in Figs. 2 and 3. From Fig. 2, one can see that TVS also performs competitively well. Moreover, in Fig. 2, one can see that Pmax is becoming higher with the increase of α . Compare Fig. 2 with Fig. 1, one can see that Pmax is the highest when α = 1.6 and Pmax is the lowest when α = 0.4 in Fig. 2, while in Fig. 1, P is the highest when α = 0.4 and P is the lowest when α = 1.6. It is known that the load heterogeneity of the network is increasing with the increase of α . It has been commonly recognized that heterogeneous networks are extremely vulnerable to the failure of a high-load node. This explains the phenomenon in Fig. 2. However, P in Fig. 1 is the average proportion of failure nodes due to the removal of an arbitrary node of the entire network. when α = 1.6, the network has load heterogeneity and most of the nodes are low-load, the removal of these nodes hardly induces cascading failure, so the average value of the whole network is relatively small. While when α = 0.4, the loads of the network are homogeneous, the failure of any one node can induce cascading failure, so the average value of the whole network is relatively large. It explains the experimental result in Fig. 1. In Fig. 3, it shows the experimental results in two real networks (UPG and UAN). In UPG, one can see that the proportion of the failure node is not simply descending with the increase of β under the new load-redistribution strategy (TVS) when α = 0.4. On the contrary, Pmax ≈ 0.014 when β ≤ 0.05 and Pmax ≈ 0.9 when 0.06 ≤ β ≤ 0.11, which indicates that the lower capacity can make the network more robust against cascading failure sometimes under TVS. Similarly, there is the same phenomenon with other values of α . On the whole, TVS performs better than FS in UPG. In UAN, compared with FS, TVS also performs better in the same condition.

Fig. 2. The relationship between β and Pmax under different strategies in two typical networks (ε i = 0): (a) BA network, (b) WS network.

Fig. 3. The relationship between β and Pmax under different strategies in two real networks (ε i = 0): (a) UPG, (b) UAN.

Then, we assume that ε i is a random number between − 1 and 1 (− 1 ≤ ε i ≤ 1). A group of random sequences between − 1 and 1 is generated by MATLAB as

where N is the total number of nodes in the complex network. From Fig. 4, one can see that the cascading failure model based on FS cannot restrain the cascading failure efficiently and a lot of nodes lose their efficacy when the loads of nodes are ever-changing. On the contrary, the model based on TVS is able to reduce the avalanche size effectively in the same conditions. It indicates that some nodes’ failure can be avoided as long as the load of the failure node is redistributed reasonably. FS cannot make full use of the residual capacity of the network, while TVS is able to redistribute the loads of failure nodes based on the current residual capacity of intact nodes. It can be illustrated as follows. Figure 5 is a simple network. According to Eq. (1), we set α = 0.5, then , , , , , , . Now we assume that node 2 is attacked. The load of node 2 will be redistributed to node 1, node 3, and node 4. When β = 0.5, according to Eq. (2), C1 = 7.3480, C3 = 2.5981, and C4 = 2.5981. The initial residual capacity of the three nodes is , , and . Without considering the time-varying load, , , , which indicates that the three nodes are all overloaded and failed in both TVS and FS situations. Then, we set β = 0.6, , , . Without considering the time-varying load, , , and . There is no cascading failure, so we investigate the utilization of the residual capacity of nodes in both TVS and FS situations considering the disturbance variable when β = 0.6. Here, we assume that the load of node 1 increased due to the existence of disturbance variable Δ l = 0.6394, , then the current residual capacity of node 1 . According to FS, , , . From the calculated results, one can see that node 1 is invalidated due to overload, while there is some unoccupied capacity in node 3 and node 4. On the contrary, according to TVS, , , , none of the nodes are invalidated. The residual capacity of node 3 and node 4 is used more fully, which avoids excessive load being redistributed to node 1. The calculated results in both FS and TVS situations illustrate that TVS can make full use of the residual capacity of the network and reduce the avalanche size effectively.

Fig. 4. The relationship between β and P under different strategies in two typical networks (− 1 ≤ ε i ≤ 1): (a) BA network, (b) WS network.

Fig. 5. A simple network.

Similarly, to further illuminate the effectiveness of TVS, we remove the node with the highest load of two typical networks and two real networks and calculate the proportion of failure nodes Pmax. Figure 6 shows the relationship between β and Pmax under different strategies in two typical networks (BA network and WS network). As shown in Fig. 6(a), the model based on FS hardly restrains the cascading failure and almost all nodes in the BA network failed, while the model based on TVS is able to reduce the size of the cascading failure effectively in the same conditions. From Fig. 6(b), one can see that the model based on FS hardly restrains the cascading failure and almost all nodes in the WS network failed, while the model based on TVS is able to reduce the size of the cascading failure effectively in the same conditions. Figure 7 shows the experimental results of two real networks. In UPG, under FS, cascading failure spreads over the entire network and almost all nodes failed. However, the network can be more robust under TVS. In UAN, TVS also performs well. In a word, TVS performs better than FS in the condition that the load of a node is time-varying.

Fig. 6. The relationship between β and Pmax under different strategies in two typical networks (− 1 ≤ ε i ≤ 1): (a) BA network, (b) WS network.

Fig. 7. The relationship between β and Pmax under different strategies in two real networks (− 1 ≤ ε i ≤ 1): (a) UPG, (b) UAN.

4. Conclusions

In this paper, we propose a load-redistribution strategy (TVS) based on ever-changing load. Compared with those strategies based on global information, the current strategy only needs local information. It is more suitable for large scale networks. Different from FS, TVS is able to make full use of the residual capacity by considering the real-time loads of nodes rather than their initial loads. In real networks, the loads of nodes are not definite values. The assumption that the loads of nodes are always their initial loads is unreasonable, so TVS is more suitable for real networks compared with FS. The results of experiments on two typical networks (BA network and WS network) and two real networks (UPG and UAN) show that TVS performs better than FS in the same conditions, especially when − 1 ≤ ε i ≤ 1. The simulation results indicate that TVS can more reasonably redistribute the loads of failure nodes to their neighbors and more effectively reduce the avalanche size than FS.

Reference
1 Liu H K and Zhou T 2007 Acta Phys. Sin. 56 106(in Chinese) [Cited within:1]
2 Cai K Q, Zhang J, Du W B and Cao X B 2012 Chin. Phys. B 21 028903 DOI:10.1088/1674-1056/21/2/028903 [Cited within:1]
3 Kinney R, Crucitti P, Albert R and Latora V 2005 Eur. Phys. J. B 46 101 DOI:10.1140/epjb/e2005-00237-9 [Cited within:1]
4 Dobson I, Carreras B A, Lynch V E and Newman D E 2007 Chaos 17 026103 DOI:10.1063/1.2737822 [Cited within:1]
5 Solé R V, Rosas-Casals M, Corominas-Murtra B and Valverde S 2008 Phys. Rev. E 77 026102 DOI:10.1103/PhysRevE.77.026102 [Cited within:1]
6 Wang G Z, Cao Y J, Bao Z J and Han Z X 2009 Acta Phys. Sin. 58 3597(in Chinese) [Cited within:1]
7 Pastor-Satorras R, Vázquez A and Vespignani A 2001 Phys. Rev. Lett. 87 258701 DOI:10.1103/PhysRevLett.87.258701 [Cited within:1]
8 Goh K I, Hahng B and Kim D 2002 Phys. Rev. Lett. 88 108701 DOI:10.1103/PhysRevLett.88.108701 [Cited within:1]
9 Chen S M, Pang S P and Zou X Q 2013 Chin. Phys. B 22 058901 DOI:10.1088/1674-1056/22/5/058901 [Cited within:1]
10 Du W B, Wu Z X and Cai K Q 2013 Physica A 392 3505 DOI:10.1016/j.physa.2013.03.032 [Cited within:1]
11 Liu G, Li Y S and Zhang X P 2013 Chin. Phys. B 22 068901 DOI:10.1088/1674-1056/22/6/068901 [Cited within:1]
12 Liu C, Du W B and Wang W X 2014 PLOS One 9 e97822 DOI:10.1371/journal.pone.0097822 [Cited within:1]
13 Duan D L and Zhan R J 2014 Acta Phys. Sin. 63 068902(in Chinese) DOI:10.7498/aps.63.068902 [Cited within:1]
14 Motter A E and Lai Y C 2002 Phys. Rev. E 66 065102 DOI:10.1103/PhysRevE.66.065102 [Cited within:2]
15 Wang W X and Chen G R 2008 Phys. Rev. E 77 026101 DOI:10.1103/PhysRevE.77.026101 [Cited within:3]
16 Lehmann J and Bernasconi J 2010 Phys. Rev. E 81 031129 DOI:10.1103/PhysRevE.81.031129 [Cited within:1]
17 Mirzasoleiman B, Babaei M, Jalili M and Safari M 2011 Phys. Rev. E 00 006100 [Cited within:1]
18 Wang J W 2013 Physica A 392 2257 DOI:10.1016/j.physa.2013.01.013 [Cited within:1]
19 Nie S, Wang X, Zhang H, Li Q and Wang B 2014 PLoS One 9 e89066 DOI:10.1371/journal.pone.0089066 [Cited within:1]
20 Wang J W and Rong L L 2009 Acta Phys. Sin. 58 3714(in Chinese) [Cited within:2]
21 Ren J L, Shen M X, Tong R and Gao H X 2011 Comput. Eng. Appl. 47 82(in Chinese) DOI:10.3778/j.issn.1002-8331.2011.33.024 [Cited within:1]
22 Duan D L and Wu X Y 2014 Acta Phys. Sin. 63 030501(in Chinese) DOI:10.7498/aps.63.030501 [Cited within:1]
23 Chen S M, Zou X Q, Lü H and Xu Q G 2014 Acta Phys. Sin. 63 028902(in Chinese) DOI:10.7498/aps.63.028902 [Cited within:1]
24 Wang J W and Rong L L 2009 Physica A 388 1289 DOI:10.1016/j.physa.2008.12.067 [Cited within:1]
25 Wang J W, Rong L L and Wang D 2010 Journal of Management Sciences in China 13 42(in Chinese) [Cited within:1]
26 Barabási A L and Albert R 1999 Science 286 509 DOI:10.1126/science.286.5439.509 [Cited within:2]
27 Watts D J and Strogatz S H 1998 Nature 393 440 DOI:10.1038/30918 [Cited within:1]
28 Albert R and Barabási A L 2002 Rev. Mod. Phys. 74 47 DOI:10.1103/RevModPhys.74.47 [Cited within:1]
29 The US power grid network dataset [Cited within:1]
30 The network of airports in the United States [Cited within:1]