The Invulnerability of Directed Interdependent Networks with Multiple Dependency Relations

Show more

1. Introduction

In recent years, there has been a significant advance in studying the proportion of complex networks. Most of the studies focus on the structure and function of single networks which do not contact with other networks [1] . But in fact, almost all networks are connected with each other, such as power grid, transportation and computer control systems. As a result, the failure in one network may cause the failure in connected networks, and vice versa. Along with this process, it may lead to cascading failure and cause serious damage. These networks are called interdependent networks [2] .

Previous studies on interdependent networks are mostly restricted by this assumption: there are two networks, network A and network B. If node a in A which depends on node b in B, node b must depend on node a [3] . However, in real-world network systems, dependent relations transmission may exit. For example, node a_{1} in A depends on node b_{1} in B, node b_{1} doesn’t depend on a_{1} and it depends on another node a_{2} in A, node a_{2} doesn’t depend on b_{1} and it depends on another node b_{2} in B. a_{1} depends on b_{1}, b_{1} depends on a_{2}, a_{2} depends on b_{2}; thus dependent relations are passed on. These networks are called directed interdependent networks.

There are two different types of dependency relations in current studies: 1) dependent―if node b depends on node a, the failure of node a must cause the failure of node b [4] . 2) supportive―if node a supports node b, the failure of node a may not cause the failure of node b; only if all nodes which support node b fail, there will be a failure of node b [5] . But it is a pity that most researchers only study one case, either dependent or supportive relation. In real-world network systems, these two types of dependency relations may exit simultaneously in one network system. For example, power grid and computer control system are connected with each other. A control center controls many generators dependently, so if there is a failure of the control center, all the generators will fail. But many generators support the control center; if a generator is failure, it may not cause the failure of the control center [6] .

This paper focuses on the invulnerability of directed interdependent networks with multiple dependency relations. Three interdependent networks have been considered: interdependent scale-free (SF) networks, interdependent Erdos-Renyi (ER) networks, and SF connected with ER network under random attack (ER network is common model for complex network research, in which each node was connected with a fix probability). Our work extends current study of interdependent network from undirected ones to directed ones, from single dependency relations to multiple dependency relations. The paper is organized as follows. In Section 2, three models will be established to study the invulnerability of interdependent networks. In Section 3, the model will be simulated in interdependent SF networks, interdependent ER networks, and SF connected with ER network. In Section 4, the conclusion got from this paper will be shown.

2. Model

An interdependent network system has been generated, which includes network A and network B. For simplicity and without loss of generality, the number of nodes in network A and B are equal. To study the invulnerability of directed interdependent networks with multiple dependency relations, we build three models: undirected interdependent networks connected by one-to-one dependent relations-UNOs; directed interdependent networks connected by one-to-one dependent relations-DNOs; directed interdependent networks connected by dependent and supportive relations-DNMs [7] . These three models are shown in Table 1 and Figures 1(a)-(c).

Supposing that a node in network A fails if it meets anyone of the following three conditions (the same as the node in network B): isolated failure (isolated in network A), dependent failure (anyone of the nodes in network B which it depends on fails) and supportive failure (all of the nodes in network B which support it fail). There are three common strategies to attack complex networks: attack based on degree, attack based on betweenness and random attack. This paper doesn’t focus on attack strategies, so that random attack is chosen as the

Table 1. All available cases studied in the paper.

(a) (b) (c)

Figure 1. (a) Undirected interdependent networks connected by one-to-one dependent relations-UNOs; (b): Directed interdependent networks connected by one-to-one dependent relations-DNOs (lines of different colors represent dependent relations of different directions: black lines represent dependent relations from network B to network A; blue lines represent dependent relations from network A to network B); (c): Directed interdependent networks connected by dependent and supportive relations-DNMs (solid line and dashed line represent different types of dependency relations respectively: solid lines represent supportive relations; dashed lines represent dependent relations).

attack strategy for simplify, which means that one node in network A is removed randomly each time. The cascading failure process of the three models is a little different [8] .

The cascading failure process of UNOs is shown below.

Step 1: Randomly remove a node in network A (remove the node together with all the edges connected to it, the same as the following ones).

Step 2: Remove the isolated node in network A and remove nodes in network B corresponding to the failing nodes in network A.

Step 3: Remove the isolated node in network B and remove nodes in network A corresponding to the failing nodes in network B.

……

The cascading failure process stops unless the number of nodes either in network A or in network B is no longer dropping.

The cascading failure process of DNOs is below.

Step 1: Randomly remove a node in network A.

Step 2: Remove the isolated node in network A and remove nodes in network B which depend on the failing nodes in network A.

Step 3: Remove the isolated node in network B and remove nodes in network A which depend on the failing nodes in network B.

……

The cascading failure process stops unless the number of nodes either in network A or in network B is no longer dropping.

The cascading failure process of DNMs is a little difficult, so that there are eight steps to describe this process.

Step 1: Randomly remove a node in the network A, and then turn to Step 2.

Step 2: Remove the isolated node in the network A and judge the dependency relations from the failing node a_{i} in the network A to b_{j} in the network B. If the relation is supportive, turn to Step 3; if the relation is dependent, remove b_{j}_{ }and turn to Step 4.

Step 3: Judge if there is any functional node in the network A that supports b_{j}. Yes, turn to Step 4; no, remove b_{j} and turn to Step 4.

Step 4: Judge if there is any node in the network B removed in the Step 2 and Step 3. Yes, turn to Step 5; no, turn to Step 8.

Step 5: Remove the isolated node in the network B and judge the dependency relations from the failing node b_{i} in the network B to a_{j} in the network A. If the relation is supportive, turn to Step 6; if the relation is dependent, remove a_{j} and turn to Step 7.

Step 6: Judge if there is any functional node in the network B that supports a_{j}. Yes, turn to Step 7; no, remove a_{j} and turn to Step 8.

Step 7: Judge if there is any node in the network A removed in the Step 5 and Step 6. Yes, turn to Step 2; no, turn to Step 8.

Step 8: Judge if there is any functional node in the network A or network B. Yes, turn to Step 1; no, end.

The form of graph has been adopted in order to express a better understanding of cascading failure process of model 3 (regard it as a stage if one network causes changes in the other network).

As shown in Figure 2(a), the node a_{2} is chosen to attack. The failure of a_{2} causes the isolation of a_{6}, so a_{6} fails (isolated failure). As shown in Figure 2(b), a_{2} fails, a_{2} cannot support b_{1} anymore and there is no node in network A supporting b_{1}, so b_{1} fails (supportive failure). By the way, the failure of a_{6} cannot cause the failure of b_{5}, because a_{3} is functional and a_{3} still supports b_{5}. The failure

(a) (b) (c) (d)

Figure 2. Description of the dynamic process of cascading failures of DNMs (transparent dots and lines represent the failure part).

of b_{1} causes the isolation of b_{5}, so b_{5} fails (isolated failure). As shown in Figure 2(c), on the one hand, b_{1} fails, and a_{1} cannot depend on b_{1}, so that a_{1} fails (dependent failure). On the other hand, b_{5} fails, and b_{5} cannot support a_{4} anymore and there is no node in network B supporting a_{4}, so that a_{4} fails (supportive failure). As shown in Figure 2(d), on the one hand, a_{1} fails, and a_{1} cannot support b_{2} anymore and there is no node in network A supporting b_{2}, so that b_{2} fails (supportive failure). On the other hand, a_{4} fails, and b_{3} cannot depend on a_{4}, so that b_{3} fails (dependent failure). The failure of b_{2} and b_{3} causes the isolation of b_{4} and b_{6}, so b_{4} and b_{6} fail. So far, all the nodes in network B fail, and the attack is over. A different situation is that the number of nodes in network A or network B is no longer dropping and the cascading failure is over, therefore, more attacks should be made to test the invulnerability of interdependent networks.

3. Simulation

In this section, the invulnerability of UNOs, DNOs and DNMs will be tested. These tested models involve three interdependent networks: interdependent SF networks, SF connected with ER network and interdependent ER networks. The number of SF network and ER network are 1000, the

Firstly, compare UNOs with DNOs whose results are presented in Figure 3 (When attack number is zero, the initial node number of all networks is 5000, this doesn’t display on the diagram). No matter for which interdependent network (SF and SF, SF and ER, SF and SF), attack number of destroying directed interdependent networks is in the range [30, 100] and attack number of destroying undirected interdependent networks is more than 2000. The attack number of destroying undirected interdependent networks is much larger than that of destroying directed interdependent networks. Meanwhile, the final attack number can be taken as a sign of the invulnerability of network system and we will use this indicator to show network system invulnerability below.

Then, compare DNOs with DNMs. Firstly, there is a consideration of one-to-one dependency relations as shown in Figure 4. As the two cases shown in Figure 4, the dependency relation from node a to node b is supportive or dependent. Let’s review dependent failure and supportive failure: anyone of the nodes which it depends on fails; all of the nodes which support it fail. If node b fails, no matter the dependency relation from node a to node b is supportive or dependent, node a will fail. Therefore, it can be understood that, in terms of the one-to-one dependency relations, the effects of supportive or dependent relations are same. The second consideration is about two-to-one dependency relations. The DNMs can be regarded as the improvement of DNOs, which means

Figure 3. The invulnerability of UNOs and DNOs (There is a big distance between attack number of undirected and directed interdependent networks. The logarithmic form is used to indicate attack number. Results are from simulations averaged about 100 realizations).

Figure 4. One-to-one dependency relations.

that DNMs is generated by adding dependent and supportive relations in the DNOs. The specific adding dependency relations rule is shown in Figure 5. Figure 5(a) can be understood like this: at the initial state, node b supports node a; now node c also supports node a, so that a supportive relation can be added from node c to node a. The realistic meaning of Figure 5(a) is to add reserve, which means that if node b fails, we can use node c to substitute. It is same as Figure 5(b): at the initial state, node a depends on node b; now node a depends on node c, so that a dependent relation can be added from node c to node a. The realistic meaning of Figure 5(b) is to add constraint, which means that not only node b but also node c is necessary to ensure node a to be functional. In addition, there may be more than one supportive and (or) dependent relation(s) added to one node in the simulation process. Due to the limitation of paper, there is no need to repeat in Figure 5(c) and Figure 5(d). By expanding on the basis of two-to-one situation, more-to-one situation can be got.

In order to get DNMs, N_{1} number of dependent relations and N_{2} number of supportive relations are added to DNOs. We assume that the original network has a total of N edges, then two variables are defined: when p = N_{1}/N, it means the increasing degree of supportive relations; when q = N_{2}/N, it means the increasing degree of dependent relations. In addition, DNOs and DNMs are directed, and N_{11} can be used to indicate the increasing number of supportive relations from network A to network B and use N_{12} to that from network B to network A. Besides, p_{1} and p_{2} are used to show the increasing degree, therefore, p = p_{1} + p_{2}. Similarly, N_{21} and N_{22} are used to indicate the increasing number of dependent relations from network A to network B and then from network B to A. As well, the use of q_{1} and q_{2} can show the increasing degree, therefore, q = q_{1} + q_{2}.

There are two factors mainly considered in this study of DNMs: the deviation to add dependency relations and the increasing number of dependency relations. The p* is used to indicate the deviation to add supportive relations and p* = p_{1} − p_{2}. If the same number of supportive relations is added from network A to

(a) (b) (c) (d)

Figure 5. The adding dependency relations rules (solid line and dashed line represent different types of dependency relations: solid lines represent supportive relation and dashed lines represent dependent ones. (a) is about adding supportive relation on the basis of itself. (b) is about adding dependent relation on the basis of itself. (c) is about adding dependent relation on the basis of supportive relation; (d) is about adding supportive relation on the basis of dependent relation).

network B and then from network B to network A, which is to add supportive relations completely symmetrically, then p* = 0. The q* is used to indicate the deviation to add dependent relations and q* = q_{1} − q_{2}. If the same number of dependent relations is added from network A to network B and then from network B to network A, which is to add dependent relations completely symmetrically, then q* = 0. In Figure 6(a), we keep p = 1, q = 0, and let p*_{ }changed within a certain range to study the impacts on the invulnerability of network systems by adding supportive relations with different deviations. As shown in Figure 6(a), in terms of the interdependent SF networks, the network invulnerability

(a) (b)

Figure 6. The invulnerability of directed interdependent networks by adding dependency relations with different deviations. (a) is about adding supportive relations. (b) is about adding dependent relations. Results are from simulations averaged about 100 realizations.

becomes the lowest one in the situation of adding supportive relations completely asymmetrically and the final attack number to destroy network system is about 200. With the tendency of adding supportive relations symmetrically, the network invulnerability increases gradually, and the network invulnerability becomes the highest one in the situation of adding supportive relations completely symmetrically with the final attack number being about 305. The tendency is the same as SF connected with ER networks and interdependent ER networks, therefore, it can be concluded that to the supportive relations, adding supportive relations symmetrically is useful to improve the invulnerability of network systems. Moreover, in terms of SF connected with ER networks, the final attack number to add supportive relations completely asymmetrically is about 215 and what to add supportive relations completely symmetrically is about 290. These two data for the interdependent ER networks are about 200 and 280 respectively. As a result, the conclusion is that, in terms of random attack, interdependent SF networks are more robust than interdependent ER networks, whose result meets well with [10] .

Then, the deviations have been studied to add dependent relations, whose result is shown in Figure 6(b). Keep p = 0, q = 1 and let q* changed within a certain range. As is shown is the result, in terms of interdependent SF networks, no matter completely adding dependent relations symmetrically or asymmetrically, the final attack number is about 19, with what to SF connected with ER networks and interdependent SF networks are about 9 and 6. Two conclusions can be made from these results: one is that, in terms of dependent relations, adding dependent relations symmetrically or asymmetrically has little effects on the invulnerability of network systems; the other is that, in terms of random attack, interdependent SF networks are more robust than interdependent ER networks.

Finally, by adding different number of supportive and dependent relations, the invulnerability of directed interdependent networks has been studied in this paper. This question involves four variables: p_{1} p_{2} q_{1} q_{2}. The question belongs to NP-hard question [11] . Limited by article length, only this situation can be under study, in which dependency relations can be completely added symmetrically. Keep p_{1} = p_{2} and q_{1} = q_{2}, and then let p and q changed within a certain range, with the result shown in Figure 7. In terms of the interdependent ER networks, the result from Figure 7(a) can be understood. With the decrease of p, the invulnerability of network systems declines and with the decrease of q, the invulnerability of network systems raises [12] . When p = 1 and q = 0, the invulnerability of network systems reaches its maximum with final attack number being about 305. When p = 0 and q = 1, the invulnerability of network systems reaches its minimum with final attack number being about 5. Meanwhile, the impacts on the invulnerability of network systems by increasing p or decreasing q are nearly equal. These results also meet well with Figure 7(b) and Figure 7(c). Therefore, it can be concluded that adding supportive relations is useful to improve the invulnerability of network systems and adding dependent relations can decline the invulnerability of network systems. The effect of raising the invulnerability of network systems by adding supportive relations almost offsets the effects on declining the invulnerability of network systems by adding the same number of dependent relations.

4. Conclusion

In this paper, with multiple dependency relations, the invulnerability of directed interdependent networks has been studied. There are two types of dependency relations: dependent relation and supportive relation, which can be found in many real-world network systems. In order to cope with the invulnerability of these networks, three models are established to extend interdependent networks from undirected to directed relations, and from single dependency relations to multiple dependency relations. These models are: undirected interdependent networks connected by one-to-one dependent relation-UNOs; directed interdependent networks connected by one-to-one dependent relation-DNOs; directed interdependent networks connected by dependent and supportive relations-DNMs. In addition, there is a simulation in interdependent SF networks, interdependent ER networks and SF connected with ER network to test the reliability of the conclusion. Comparing the UNOs with the DNOs, it is shown that the invulnerability of undirected interdependent networks is much higher than that of directed interdependent networks [13] . This reason may be that there is too much dependent relation transmission in directed interdependent networks. Therefore, in real-world, if we want to build a survivable interdependent network, we’d better choose undirected network. Comparing the DNOs with the DNMs, two conclusions can be drawn: one is that adding supportive relations symmetrically is useful to improve the invulnerability of network systems [14]

(a) (b) (c)

Figure 7. The invulnerability of directed interdependent networks by adding different number of supportive and dependent relations. (a) is about interdependent SF networks. (b) is about SF connected with ER networks. (c) is about interdependent ER network. There is a big distance between final attack number of directed interdependent networks with different number of increasing supportive and dependent relations. As a result, the logarithmic forms are used to indicate final attack number. Results are from simulations averaged about 100 realizations.

and adding dependent relations symmetrically or asymmetrically has little effects on the invulnerability of network systems; the other is that adding supportive relations can improve the invulnerability of network systems [15] and adding dependent relations can decline the invulnerability of network systems. The effect of raising the invulnerability of network systems by adding supportive relations almost offsets the effect on declining the invulnerability of network systems by adding the same number of dependent relations. Therefore, to improve the invulnerability of given network, regarding to whether to add supportive relation or reduce dependent relation, other factors (such as cost) should be considered. And if we choose to add supportive relations, we’d better add supportive relations symmetrically. Last but not least, in this paper, we study the The Invulnerability of Directed Interdependent Networks with Multiple Dependency Relations from the perspective of simulation, future work can be made to study it from the analytic angle.

References

[1] Gao, J.X., Li, D.Q. and Havlin, S. (2014) From a Single Network to a Network of Networks. National Science Review, 1, 346-356.

[2] Shin, D.H., Qian, D. and Zhang, J. (2014) Cascading Effects in Interdependent Networks. IEEE Network, 28, 82-87.

https://doi.org/10.1109/MNET.2014.6863136

[3] Chen, L., Peng, J. and Zhang, B. (2017) Uncertain Goal Programming Models for Bicriteria Solid Transportation Problem. Applied Soft Computing, 51, 49-59.

https://doi.org/10.1016/j.asoc.2016.11.027

[4] Hu, Y., Zhou, D. and Zhang, R. (2013) Percolation of Interdependent Networks with Inter-Similarity. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 88, Article ID: 052805.

https://doi.org/10.1103/PhysRevE.88.052805

[5] Dong, G., Tian, L. and Zhou, D. (2013) Robustness of Interdependent Networks with Partial Support-Dependence Relationship. Europhysics Letters, 102, Article ID: 68004.

https://doi.org/10.1209/0295-5075/102/68004

[6] Chen, L., Peng, J. and Zhang, B. (2017) Uncertain Programming Model for Uncertain Minimum Weight Vertex Covering Problem. Journal of Intelligent Manufacturing, 28, 625-632.

https://doi.org/10.1007/s10845-014-1009-1

[7] Gao, X.L. (2018) Cycle Index of Uncertain Random Graph. Journal of Intelligent and Fuzzy Systems, 34, 4249-4259.

https://doi.org/10.3233/JIFS-17373

[8] Cheng, L., Rao, C.J. and Chen, L. (2017) Multidimensional Knapsack Problem Based on Uncertain Measure. Scientia Iranica, 24, 2527-2539.

[9] Fu, G.H., Dawson, R. and Khoury, M. (2014) Interdependent Networks: Vulnerability Analysis and Strategies to Limit Cascading Failure. The European Physical Journal B, 87, 148.

https://doi.org/10.1140/epjb/e2014-40876-y

[10] Cheng, Z.S., Cao, J.D. and Hayat, T. (2015) Cascade of Failures in International Networks with Different Average Degree. International Journal of Modern Physic C, 25, Article ID: 1440006.

[11] Cheng, L., Rao, C., Chen, L. and Rosyida, I. (2016) A Belief Degree Constrained Programming Model for Maximum Cut Problem with Uncertain Edge Weights. ICIC Express Letters, Part B: Applications, 7, 1185-1191.

[12] Zhang, P., Cheng, B.S. and Zhao, Z. (2013) The Robustness of Interdependent Transportation Networks under Targeted Attack. Europhysics Letters, 103, Article ID: 68005.

https://doi.org/10.1209/0295-5075/103/68005

[13] Gao, J., Buldyrev, S. and Stanley, H.E. (2013) Percolation of a General Network of Networks. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 88, Article ID: 062816.

https://doi.org/10.1103/PhysRevE.88.062816

[14] Martin-Hernandez, J., Wang, H. and Van Mieghem, P. (2014) Algebraic Connectivity of Interdependent Networks. Physica A: Statistical Mechanics and Its Applications, 404, 92-105.

https://doi.org/10.1016/j.physa.2014.02.043

[15] Zhou, D., Gao, J. and Stanley, H.E. (2013) Percolation of Partially Interdependent Transportation Networks under Targeted Attack. Europhysics Letters, 103, Article ID: 68005.

https://doi.org/10.1209/0295-5075/103/68005