Vulnerability Assessment for Cascading Failures in Interdependent Networks

Abstract

INTRODUCTION Modern life is supported by mutually dependent complex networks such as electricity, communication or transportation networks. In recent years, potential risks behind such interdependency have been recognized. For example, a failure in communication network can cause serious problems in transport network. As the complexity and interaction strength increase, such systems can create uncontrollable situations1). It is extremely difficult to predict and/or control spreading of failures in such interdependent network systems2). When a local failure occurs in one network, this may trigger continuous failures in the same network. When the networks are dependent each other, the sequence of failures is not limited to the firstly damaged network. The interdependency across different networks generates continuous breakdowns in other networks. As a result, mutually dependent network systems suffer catastrophic damage as a whole. This phenomenon is referred to “cascading failures in interdependent networks”. This study aims to analyze the effects of the strength of dependency on the vulnerability to cascading failures. Most of the preceding studies have focused on the limited case of a single and isolated network3)-8). Only a few papers have conducted research on interdependent networks, but almost all of them have turned their eyes on the fully interdependent case2), 9). Weak interdependency may change a robust network into extremely fragile one. Thus, the degree of interdependency on cascading failures of network systems should be studied in detail. METHODOLOGY (1) ASSUMPTIONS FOR INTERDEPENDENT NETWORKS As shown in Fig. 1, this study targets mutually dependent two networks, A and B, with the same number of nodes. A node in network A is connected to a node in network B. Number of links in two networks can be different. For simplicity, network flow is assumed that one unit of the quantity is exchanged between every pair of nodes along the shortest path in each network. The flow in network A remains within the network and does not enter to network B, and vice versa. The interdependency is assumed to be one-on-one correspondence between nodes of two networks. and denote the connected nodes in network A and B, respectively. The functioning of node depends on the ability of node , and vice versa. If node is broken, node which depends on node can be also broken with a probability indicating the degree of dependency of network A on network B. denotes the probability for network B. corresponds to the case of two independent networks, and corresponds to the fully interdependent case.

Fig. 1 Interdependent networks (2) MODEL FOR CASCADING FAILURES Cascading failure in this study refers to a phenomenon that damaged nodes and links are removed one after another from two networks. Model for cascading failures in interdependent networks consists of four parts, a) normal state, b) initial failure, c) sequence of failures, and d) ultimate state. a) Normal state In the normal state, all nodes of each network are connected and one unit of the quantity is exchanged between every pair of nodes. The load of node is equal to the betweenness centrality of node ,

(1)

where is a set of nodes in network A, is the number of the shortest paths between a pair of two nodes in network A, and is the number of the shortest paths passing through 7). The betweenness centrality of a node is equivalent to the traffic flow through the node when unit OD matrix is assigned to the shortest path. The capacity of a node is the maximum load that the node can handle. The capacity of node is assumed to be proportional to its initial load ,

(2)

where the constant denotes the capacity parameter, that is prepared for discussing the effects of the mergin of the capacity on the vulnerability of the networks. and in network B are also defined as the same manner. We assume that a link does not have its capacity. b) Initial failure An initial failure occurs at a single pair of nodes in networks A and B, , these nodes are removed from the networks. This initial failure can change the shortest paths and flows in each network, which can trigger continuous breakdowns. c) Sequence of failures The chain of failures is divided into two parts, failures caused by overload in each network and failures caused by dependency between two networks.

Assume that, after the initial failure, these two types of failures occur by turns until the network conditions converge to the ultimate state shown below. When the shortest paths in each network change due to the failures of nodes, the load of node can be also represented by Eq. (1). Only the difference is that a normal node set is substituted by a set of alive nodes in a damaged network. If the load of a node exceeds its capacity, the node is removed with its connecting links from the network. The overload failures are calculated in both network A and B, respectively. On the other hand, the failures in one network can be propagated to the other network due to dependency between two networks. If node is broken, node which depends on node can be also broken with a probability . If node is broken, node is removed with its links from network A. This process occurs as the same in network B. d) Ultimate state The set of alive nodes will shrink with the sequence of failures, and result to the decrease of the overall loads to the network. If the load of every alive node is smaller than the capacity of the node, the sequence of failures terminates and two networks settle in a certain state. This state is defined as the ultimate state:

(3)

(4)

where is the load of node and is a set of alive nodes in network A at the ultimate state. and are also defined in the same way. (3) DAMAGE EVALUATION Damage is defined as the ratio of the number of a damaged pair of nodes with the number of a pair of nodes in the normal network. This is represented by;

(5)

where denotes the damage of network A, is the number of connected pair of nodes in network A in the normal state, and is the number of connected pair of nodes in network A in the ultimate state. The damage of network B is also defined. Initial failure may occur for every pair of nodes, thus, the damage is calculated for every initial node failure and then the average value of the damage is evaluated. NUMERICAL EXAMPLE

We prepared two different networks for numerical caluculation. One is SmallWorld (SW) network10) as a relatively fragile network and the other is ScaleFree (SF) network11) as a highly robust network. Both SW and SF networks have 200 nodes. Fig. 2 shows the damage of two networks in symmetrical case assuming that the strength of dependency represented by the value of dependency probability is the same for two networks; . For different values of capacity parameter , the damages of SW network and SF network are caluculated.

Fig. 2 Damage evaluation of SW-SF networks According to Fig. 2, SF can turn into extremely fragile when it depends on SW. If the capacity parameter is equal to 0.5, the damage of both SW and SF shows a gradually increasing from 0.05 to 0.25. However, when the capacity parameter is equal to 0.2, there is a remarkable increase from 0.05 to 0.75. The damage rises greatly even when the strength of dependency is small. SF network is robust as a single independent network, however, it becomes fragile when it is connected with SW network. CONCLUSIONS This study shows a simple methodology for assessing the vulnerability to cascading failures in interdependent networks. The numerical example implies the vulnerability can increase greatly even if the mutual dependency of two networks is not so strong. There is a risk of underestimating network vulnerability when we ignore the interdependency of network systems. By introducing the degree of dependency, this model can be easily applied to asymmetrical interdependent cases; . Case studies will be presented in the conference presentation. REFERENCES 1) Helbing, D. : Globally networked risks and how to respond, Nature, Vol. 497, No. 7447, pp. 51-59, 2013. 2) Vespignani, A. : Complex networks: The fragility of interdependency, Nature, Vol. 464, No. 7291, 984-985, 2010. 3) Buzna, L., Peters, K., Ammoser, H., Kühnert, C. and Helbing, D. : Efficient response to cascading disaster spreading, Physical Review E, Vol. 75, No. 5, 056107, 2007. 4) Buzna, L., Peters, K. and Helbing, D. : Modelling the dynamics of disaster spreading in networks, Physica A: Statistical Mechanics and its Applications, Vol. 363, No. 1, pp. 132-140, 2006. 5) Crucitti, P., Latora, V. and Marchiori, M. : Model for cascading failures in complex networks, Physical Review E, Vol. 69, No. 4, 045104, 2004.

6) Motter, A. E. : Cascade control and defense in complex networks, Physical Review Letters, Vol. 93, No. 9, 098701, 2004. 7) Motter, A. E. and Lai, Y. C. : Cascade-based attacks on complex networks, Physical Review E, Vol. 66, No. 6, 065102, 2002. 8) Simonsen, I., Buzna, L., Peters, K., Bornholdt, S. and Helbing, D. : Transient Dynamics Increasing Network Vulnerability to Cascading Failures, Physical Review Letters, Vol. 100, 218701, 2008. 9) Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E. and Havlin, S. : Catastrophic cascade of failures in interdependent networks, Nature, Vol. 464, No. 7291, pp. 1025-1028, 2010. 10) Watts, D. J. and Strogatz, S. H. : Collective dynamics of ‘small-world’ networks, Nature, Vol. 393, No. 6684, pp. 440-442, 1998. 11) Barabási, A. L. and Albert, R. : Emergence of scaling in random networks, Science, Vol. 286, No. 5439, pp. 509-512.509-512 1999.