# Vulnerability Analysis of Interdependent Scale-Free Networks with Complex Coupling

Authors: Chunjie Cao; Zhiqiang Zhang; Jingzhang Sun; Xianpeng Wang; Mengxing Huang
Journal: Journal of Electrical and Computer Engineering
 (2017)

---

## Abstract

Recent studies have shown that random nodes are vulnerable in interdependent networks with simple coupling. However, relationships in actual networks are interrelated and complex coupling. This paper analyzes the vulnerability of interdependent scale-free networks with complex coupling based on the BA model. The results indicate that these networks have the same vulnerability against the maximum node attack, the load of the maximum node attack, and the random node attack, which explain that the coupling relationship between network nodes is an important factor in network design.


---

## Body

## 1. Introduction

The small-world network model [1] (Watts and Strogatz, 1998) and the scale-free network model [2] (Barabasi and Albert, 1999) inspired research on complex networks. At present, research of complex networks penetrates into almost all fields such as computer networks, social networks, and biological networks. Based on the small-world network model and scale-free network model, researchers have improved the moment conditions. In the field of computer networks, researchers presented an algorithm for building a new small-world network model by combining the two archetypal small-world networks [3], which can better describe the real instant messaging chat network. In the research of the social networks, researchers established a navigable small-world network based on game-theory model [4] and used this to solve the problem of reciprocity and navigability in social networks. In terms of biological networks, researchers found that the FRC network topology is highly robust and revealed the critical role of the network integrity in the activation of adaptive immune responses [5]. Researchers continue to improve the complex network model and laid the foundation for the research of complex network theory.Currently, network vulnerability analysis is a very important topic in the theoretical research of complex networks, which mainly studies the problem of vulnerability of complex networks under various attacks (such as deliberate attacks and random failures), especially the vulnerability of an interdependent network system. Recently, domestic and foreign scholars have carried out a series of researches on the impact of the complex network vulnerability and triggered cascading failures. In order to analyze constantly changing impact of component failure propagation on the system, Cheng et al. proposed an optimizing model based on game theory [6]. They found that the failure of components has a great negative impact on the physical network system and used a linear programming method to solve this problem. As for how to effectively model critical infrastructures with interdependent relationships, Rinaldi established the interdependent network system using dynamic simulation and identified the range of cascading security operation [7]. According to the complex relationship between the power system and the rapid processing data network, Cai et al. established an interdependent network model to analyze the complex effects caused by cascading failures [8]. The modern society relies on the complex network of critical infrastructure systems (such as power networks, telecommunication networks, transportation networks, and water supply systems). Although urban communities rely on each independent infrastructure, recent disasters, such as hurricanes, large-scale power outages, and terrorist attacks, have shown that the most dangerous vulnerabilities were hidden between different interdependencies infrastructures. In a system, the failure of a subsystem is likely to result in the failure of the other, and then the failure of cascading is triggered. On September 28, 2003, a power plant in Italy’s grids failed, which led to disabling of the corresponding Internet node. This also resulted in other power stations going offline. Eventually, this effect caused a blackout in the southern peninsula [9]. Regarding this event, Buldyrev et al. published the results of a study (April 2010, Nature) [10] showing that the coupled complex network system facing random faults is also fragile.Buldyrev et al.’s conclusion reveals the effect of network dependence on network vulnerability. However, as Vespignani said, Buldyrev et al.’s model is simply coupled and ideal. It cannot reflect the complex dependency relationship of actual network systems [11]. This BA model based paper studies the network vulnerability of scale-free networks with complex dependency. Results show that the scale-free networks with complex dependencies are vulnerable against the node of the maximum degree, the node of the maximum load, and the random node attack, and when a single node is attacked, most nodes in the network are compromised. This presents a serious challenge to the complex network systems’ design and optimization.


## 2. Network Model

In recent years, researchers have discovered many complex networks, including the Internet, WWW, and metabolic networks; all these networks’ connection degree distribution functions have power laws [12–15]. There is no obvious feature length in these networks’ nodes connectivity. These networks are called scale-free networks. Currently, researchers propose many optimized methods for the scale-free networks model by using sparse matrix vector multiplication to construct scale-free networks [16], using the internal weighted average method to calculate the configuration parameters of scale-free networks [17], and using boosting regression algorithm and Bayesian algorithm to construct prior information and establish the scale-free networks based on prior information [18]. Random scale-free networks are modeled with chain fault [19]. We add the strategy of multiscale networks to generate artificial neural networks when constructing scale-free networks, which is used to simulate the network performance of the multiscale [20].


### 2.1. BA Network Model

Barabasi and Albert proposed a scale-free network model (BA model) to describe two important features of actual networks.(i) Growth characteristic: the network scale is expanding. As a large number of new articles are published every month, such as on the WWW, there are a lot of new web pages every day.(ii) Priority connection characteristic: the new node tends to connect with nodes with a higher degree. This phenomenon is called “the rich get richer effect” or “Matthew effect.”Based on the growth characteristic and priority connection characteristic, the algorithm for constructing the BA scale-free network model is as follows.(iii) Growth: the network starts withm0 nodes, with the addition of a new node and chain to the m existing nodes, where m≤m0.(iv) Priority connection: definePi as the probability of a new node connecting with node i. The relationship between Pi, degree ki of node i, and degree kj of node j is as follows:(1)Pi=ki∑jkj.(v) Aftert steps, the BA model construction algorithm generates a network with N=t+m nodes and mt edges.


### 2.2. Complex Coupling Interdependent Scale-Free Network

Based on the BA scale-free network model constructing algorithm, altogether, at leastT=100 samples are made, each time generating two scale-free networks (A and B) with 1000 nodes, as shown in Figures 1-2, and randomly generating coupling coefficient matrixes (MAB and MBA) existing in between networks A and B, as shown in Figures 3-4. If MAB(i,j)=1, then nodes Ai and Bj will have a coupling relationship; that is, if node Ai loses, node Bj fails. If MAB(i,j)=0, then nodes Ai and Bj will have no coupling relationship; that is, node Ai loses, while node Bj is validated. Coupling coefficient matrix depicts that the relationship of interdependence network nodes does not have to be a two-way direct coupling relationship. And this method also reflects the reality of actual networks. In the network model proposed by Buldyrev et al., interdependence network nodes have a two-way direct coupling relation. That is, if node Ai loses, node Bj fails, and there is no influence on other nodes. And if node Bj loses, node Ai also fails. However, in the actual network, coupling relationships among different network nodes are complex; node Ai possibly has a coupling relationship with node Bj1 or may have a coupling relationship with node Bj2. And node Bj loss does not necessarily result in node Ai failure (e.g., Internet, WWW, and electric power networks). This is our improvement on Buldyrev et al.’s network model.Figure 1
Scale-free network A.Figure 2
Scale-free network B.Figure 3
Coupling coefficient matrixMAB.Figure 4
Coupling coefficient matrixMBA.


## 2.1. BA Network Model

Barabasi and Albert proposed a scale-free network model (BA model) to describe two important features of actual networks.(i) Growth characteristic: the network scale is expanding. As a large number of new articles are published every month, such as on the WWW, there are a lot of new web pages every day.(ii) Priority connection characteristic: the new node tends to connect with nodes with a higher degree. This phenomenon is called “the rich get richer effect” or “Matthew effect.”Based on the growth characteristic and priority connection characteristic, the algorithm for constructing the BA scale-free network model is as follows.(iii) Growth: the network starts withm0 nodes, with the addition of a new node and chain to the m existing nodes, where m≤m0.(iv) Priority connection: definePi as the probability of a new node connecting with node i. The relationship between Pi, degree ki of node i, and degree kj of node j is as follows:(1)Pi=ki∑jkj.(v) Aftert steps, the BA model construction algorithm generates a network with N=t+m nodes and mt edges.


## 2.2. Complex Coupling Interdependent Scale-Free Network

Based on the BA scale-free network model constructing algorithm, altogether, at leastT=100 samples are made, each time generating two scale-free networks (A and B) with 1000 nodes, as shown in Figures 1-2, and randomly generating coupling coefficient matrixes (MAB and MBA) existing in between networks A and B, as shown in Figures 3-4. If MAB(i,j)=1, then nodes Ai and Bj will have a coupling relationship; that is, if node Ai loses, node Bj fails. If MAB(i,j)=0, then nodes Ai and Bj will have no coupling relationship; that is, node Ai loses, while node Bj is validated. Coupling coefficient matrix depicts that the relationship of interdependence network nodes does not have to be a two-way direct coupling relationship. And this method also reflects the reality of actual networks. In the network model proposed by Buldyrev et al., interdependence network nodes have a two-way direct coupling relation. That is, if node Ai loses, node Bj fails, and there is no influence on other nodes. And if node Bj loses, node Ai also fails. However, in the actual network, coupling relationships among different network nodes are complex; node Ai possibly has a coupling relationship with node Bj1 or may have a coupling relationship with node Bj2. And node Bj loss does not necessarily result in node Ai failure (e.g., Internet, WWW, and electric power networks). This is our improvement on Buldyrev et al.’s network model.Figure 1
Scale-free network A.Figure 2
Scale-free network B.Figure 3
Coupling coefficient matrixMAB.Figure 4
Coupling coefficient matrixMBA.


## 3. Vulnerability Analysis

In many real networks, a single or a few failed nodes or failed edges (this fault may happen randomly or may be due to a deliberate attack) can cause other nodes to break down through the coupling relationships between nodes and then cause a chain reaction, eventually causing the breakdown of a lot of nodes, even the entire network. This phenomenon is called cascading failure, sometimes called “avalanche” phenomenon. This phenomenon is a widespread problem in traffic networks, Internet networks, power networks, social and economic networks, and other real complex networks.We perform an analysis based on the above network model and attack the node of maximum degree, the node of maximum load, and the random node in network A by using the maximum degree node attack, the maximum load node attack, and the random node attack, negate the effects of the node, and then observe the effect of connectedness of network B. The connectivity is analyzed through the quantity of nodes contained in the maximal connected subset (subgraph) in network B; as shown in Figures5–7, the nodes of maximum degree and random nodes are easy to select and calculate, and selection of the maximum load node uses the betweenness of the node as a selection standard. Betweenness adopts the Floyd algorithm to calculate the shortest path between nodes of network A.Figure 5
Maximum node attack.Figure 6
Node of maximum load attack.Figure 7
Random node attack.From a large amount of data analysis under three attack modes, we can see that nonscale networks maintained a similar network topology, and the scale of the largest connected subgraph is approximately equal. As shown in Figure8, the straight line in the graph is the average value of the maximal connected subgraph under three attack methods. In this figure’s bottom left corner is the probability distribution maximal connected subgraph under three attack methods. Statistical results show that the three attack methods have the same influence on the scale of the largest connected subgraph node of scale-free networks with complex coupling relationships. From the perspective of connectivity, the attack caused the decline of the network performance by 90%.Figure 8
Connected subset size contrast.


## 4. Conclusion

The model proposed by Buldyrev et al. is simply coupled and ideal. It cannot fully present the complicated dependence of the actual network system. This paper studies scale-free networks with complex dependency based on the BA model. Results show that the scale-free networks with complex dependencies are vulnerable against the node of the maximum degree, the node of the maximum load, and the random node attack, and when a single node is attacked, most nodes in the network are compromised. This presents a serious challenge to the complex network systems’ design and optimization. Therefore, the coupling between networks must be taken into account in the design of reliable systems.



---

*Source: 9080252-2017-08-14.xml*