# Interdependency and Vulnerability of Multipartite Networks under Target Node Attacks

Authors: Qing Cai; Mahardhika Pratama; Sameer Alam
Journal: Complexity
 (2019)

---

## Abstract

Complex networks in reality may suffer from target attacks which can trigger the breakdown of the entire network. It is therefore pivotal to evaluate the extent to which a network could withstand perturbations. The research on network robustness has proven as a potent instrument towards that purpose. The last two decades have witnessed the enthusiasm on the studies of network robustness. However, existing studies on network robustness mainly focus on multilayer networks while little attention is paid to multipartite networks which are an indispensable part of complex networks. In this study, we investigate the robustness of multipartite networks under intentional node attacks. We develop two network models based on the largest connected component theory to depict the cascading failures on multipartite networks under target attacks. We then investigate the robustness of computer-generated multipartite networks with respect to eight node centrality metrics. We discover that the robustness of multipartite networks could display either discontinuous or continuous phase transitions. Interestingly, we discover that larger number of partite sets of a multipartite network could increase its robustness which is opposite to the phenomenon observed on multilayer networks. Our findings shed new lights on the robust structure design of complex systems. We finally present useful discussions on the applications of existing percolation theories that are well studied for network robustness analysis to multipartite networks. We show that existing percolation theories are not amenable to multipartite networks. Percolation on multipartite networks still deserves in-depth efforts.


---

## Body

## 1. Introduction

Complex systems are ubiquitous in our daily lives. The form of a complex system ranges from the macroscopic level like the power grid systems [1] to the microscopic level like the metabolic systems [2]. In order to better understand and control complex systems, a widely adopted method is to model a complex system as a network that is composed of a set of nodes and edges with the nodes denoting the network’ components and the edges denoting the relations between components [3]. It has been proved that complex network modelling and analysis are a promising instrument for not only control science [4–7] but also data science [8–10].Note that a complex network in reality is likely to suffer from attacks and failures of network components [11–13]. Because the components of a complex network are interconnected [14, 15], therefore the failures of some components are likely to trigger the failures of other components that depend on those failed components and cascading failures occur [16, 17]. As a result, a small fraction of component failures may lead to the breakdown of the whole network [18–21]. In order to evaluate the robustness of complex networks under perturbations, studies on network robustness emerged and have gained a great popularity in the past two decades [22–26]. In the literature, a large body of work has been done towards network robustness [27–31].Network robustness has long been studied [32–36]. During a long period of time, robustness studies mainly exploit the robustness of single networks [37]. It has been widely reported that the robustness of single networks normally displays a continuous phase transition phenomenon [17, 38, 39], which indicates that single networks are robust to perturbations. Note that networks in reality are not independent but on the contrary interact with one another, forming multilayer networks [40–44]. A small fraction of component failures in a multilayer network can elicit cascading failures [45, 46]. It has been disclosed that the robustness of multilayer networks normally exhibits a discontinuous phase transition phenomenon [14, 45, 47], which indicates that multilayer networks are vulnerable to perturbations [15, 18, 24].The seminal work in [45] has sparked the research enthusiasm on the robustness of multilayer networks. An enormous amount of outstanding work has been done by researchers towards network robustness analysis [48–53]. Existing studies can be roughly categorised into three groups, i.e., studies on network robustness to node failures [54–59], studies on network robustness to edge failures [46, 60–62], and studies on network robustness to community failures [63–66]. A community is generally referred to as a subgraph of a network that has dense interconnections but sparse connections with the rest of the network [67–73]. It should be pointed out that, apart from multilayer networks, there exists another kind of network called multipartite networks, which are an indispensable part of complex networks [3, 74]. A multipartite network generally refers to a network whose nodes can be divided into several sets or layers while its edges only occur between two neighbouring node sets or layers (see Section 2.2 for the mathematical definition). A handful of complex networks such as service supplier-user networks [75], economic networks [76], ecological networks [77], and biological networks [78] could be modeled as multipartite networks.Investigating the robustness of multipartite networks is significantly pertinent to unravel system dynamics of multipartite networks. In the literature, studies on the robustness of multipartite networks only deal with the simplest scenarios, namely, bipartite networks. Although existing studies indicate that bipartite networks are robust to attacks [56, 79, 80], how multipartite networks behave in face of attacks is still unknown. Meanwhile, existing studies are primarily from specific domains like ecology [56, 64, 65], biology [79], and economy [80], i.e., the robustness analysis of bipartite networks depends on domain-specific knowledge. Albeit the nature of studies on the robustness of multilayer networks [15, 81], existing models and theories cannot be directly applied to multipartite networks. The key reason is that the structures of multipartite networks differ from that of multilayer networks.In order to understand how multipartite networks behave in the presence of attacks, in this paper we present a simulation-based study to capture a fundamental comprehension of the robustness of multipartite networks. To do so, we first put forward two network models to mimic the dynamic processes on multipartite networks under target node attacks. Subsequently, we examine the robustness of multipartite networks under target node attacks with respect to eight widely investigated node centrality metrics, which are the Degree centrality, Betweenness centrality, Closeness centrality, EigenVector centrality, Coreness centrality, Subgraph centrality, PageRank centrality, and LocalRank centrality. Finally, we carry out extensive experiments on multipartite networks with Poisson degree distributions. The experiments indicate that the robustness of multipartite networks could display either discontinuous or continuous phase transitions, depending on the utilized network models. As a multipartite network could be regarded as a simplified multilayer network from the viewpoint of network structures, therefore we apply existing percolation theories that are developed for robustness analysis of multilayer networks to the case of multipartite networks. We show that existing percolation theories are not applicable to multipartite networks. It has been reported that the robustness of a multilayer network deteriorates sharply with the increase of the number of network layers. Surprisingly, we in this work have experimentally found that the robustness a multipartite network does not vary too much with respect to the change of the number of its node sets. The experiments even show that the increase of the number of the node sets could increase the robustness of a multipartite network. Our study suggests that multipartite networks are more robust to attacks than multilayer networks do.The remainder of this paper is structured as follows. Section2 presents some preliminaries for better understanding of this work. Section3 discusses the research motivations. Section4 demonstrates our empirical method for exploring the robustness of multipartite networks under target node attacks. Section5 displays the simulation experiments on multipartite networks with Poisson degree distributions and Section 6 concludes the paper.


## 2. Preliminary

### 2.1. Complex Network Notations

In the literature, a commonly used method for complex network analytics is to denote a network by a graph which is generally denoted byG=V,E with V representing the set of nodes and E the set of edges. The edges between the nodes of G can be reflected by the adjacency matrix A of G. The entry aij of A is normally defined as follows:(1)aij=1,ifeij∈E,aij=0,ifeij∉E.Concerning complex network analytics, one of the most frequently discussed terms is degree. The degreedi of node i is defined as di=∑jaij, i.e., di equals the number of edges that have been attached to node i.


### 2.2. Multipartite Networks

Given a networkG=V,E. Assume that V can be divided into L subsets, i.e., V=V1,V2,…,VL. If ∀a,b∈1,L, G satisfies the following conditions:(2)Va∩Vb=∅,ifa≠b,aij∈0,1,ifi∈Va∧j∈Vb∧b=a−1,aij∈0,1,ifi∈Va∧j∈Vb∧b=a+1,aij≡0,ifi∈Va∧j∈Va±k,∀k∈2,L−1,aij≡0,ifi,j∈Va,then G is called a multipartite network [19, 74].Note that the subsetVi also can be called a partite set [19, 74]. Thus, a multipartite network with L-partite sets is deemed an L-partite network. Especially, an L-partite network with L=2 is normally termed as a bipartite network [19, 74].Equation (2) indicates that there is no edge between nodes within the same node set. If we relax this condition, i.e., edges between nodes within the same node set are allowed, then a network with such kind of structure is normally called a multilayer network [43, 44, 82]. Mathematical definitions for multilayer networks can be found in [41, 42].Figure1(a) gives a graphical example of a three-layer network which is composed of three networks G1, G2, and G3 (denoted by different colors), while Figure 1(b) presents a graphical example of a multipartite network with three partite sets, i.e., a tripartite network. From the perspective of network structures, we can observe from Figures 1(a) and 1(b) that a multipartite network can be regarded as a simplified multilayer network.Figure 1
Graphical illustrations of (a) a multilayer network consisting of three networksG1, G2, and G3 and (b) a multipartite network consisting of three partite sets V1, V2, and V3.


### 2.3. Network Robustness

Studies on network robustness aim at evaluating the endurance of a network in face of perturbations. In the literature, there are mainly two widely adopted methods for network robustness analysis. Figure2 explains the main ideas of those two methods.Figure 2
Ideas of two widely adopted methods for network robustness analysis. (a) Idea of the method based on the calculation ofrq, i.e., the fraction of nonzero degree nodes after removing q fraction of the nodes from a network [56, 60, 65]. (b) Idea of the method based on the calculation of P∞, i.e., the fraction of nodes in the largest connected component of a network after removing 1−p fraction of its nodes [16, 21, 45].
(a)
(b)The method shown in Figure2(a) pays attention to the fraction rq of nonzero degree nodes after removing q fraction of nodes from a focal network. The method shown in Figure 2(b) focuses on the fraction LCC/N of nodes in the largest connected component (LCC) after removing a given fraction 1−p of nodes. The above two methods then, respectively, measure the robustness of a network as follows:(3)Rn=∑q=01rq,P∞=LCCN,where the symbols Rn and P∞ quantify the robustness of a network. Normally, the larger the values of Rn and P∞are, the more robust the network is.


## 2.1. Complex Network Notations

In the literature, a commonly used method for complex network analytics is to denote a network by a graph which is generally denoted byG=V,E with V representing the set of nodes and E the set of edges. The edges between the nodes of G can be reflected by the adjacency matrix A of G. The entry aij of A is normally defined as follows:(1)aij=1,ifeij∈E,aij=0,ifeij∉E.Concerning complex network analytics, one of the most frequently discussed terms is degree. The degreedi of node i is defined as di=∑jaij, i.e., di equals the number of edges that have been attached to node i.


## 2.2. Multipartite Networks

Given a networkG=V,E. Assume that V can be divided into L subsets, i.e., V=V1,V2,…,VL. If ∀a,b∈1,L, G satisfies the following conditions:(2)Va∩Vb=∅,ifa≠b,aij∈0,1,ifi∈Va∧j∈Vb∧b=a−1,aij∈0,1,ifi∈Va∧j∈Vb∧b=a+1,aij≡0,ifi∈Va∧j∈Va±k,∀k∈2,L−1,aij≡0,ifi,j∈Va,then G is called a multipartite network [19, 74].Note that the subsetVi also can be called a partite set [19, 74]. Thus, a multipartite network with L-partite sets is deemed an L-partite network. Especially, an L-partite network with L=2 is normally termed as a bipartite network [19, 74].Equation (2) indicates that there is no edge between nodes within the same node set. If we relax this condition, i.e., edges between nodes within the same node set are allowed, then a network with such kind of structure is normally called a multilayer network [43, 44, 82]. Mathematical definitions for multilayer networks can be found in [41, 42].Figure1(a) gives a graphical example of a three-layer network which is composed of three networks G1, G2, and G3 (denoted by different colors), while Figure 1(b) presents a graphical example of a multipartite network with three partite sets, i.e., a tripartite network. From the perspective of network structures, we can observe from Figures 1(a) and 1(b) that a multipartite network can be regarded as a simplified multilayer network.Figure 1
Graphical illustrations of (a) a multilayer network consisting of three networksG1, G2, and G3 and (b) a multipartite network consisting of three partite sets V1, V2, and V3.


## 2.3. Network Robustness

Studies on network robustness aim at evaluating the endurance of a network in face of perturbations. In the literature, there are mainly two widely adopted methods for network robustness analysis. Figure2 explains the main ideas of those two methods.Figure 2
Ideas of two widely adopted methods for network robustness analysis. (a) Idea of the method based on the calculation ofrq, i.e., the fraction of nonzero degree nodes after removing q fraction of the nodes from a network [56, 60, 65]. (b) Idea of the method based on the calculation of P∞, i.e., the fraction of nodes in the largest connected component of a network after removing 1−p fraction of its nodes [16, 21, 45].
(a)
(b)The method shown in Figure2(a) pays attention to the fraction rq of nonzero degree nodes after removing q fraction of nodes from a focal network. The method shown in Figure 2(b) focuses on the fraction LCC/N of nodes in the largest connected component (LCC) after removing a given fraction 1−p of nodes. The above two methods then, respectively, measure the robustness of a network as follows:(3)Rn=∑q=01rq,P∞=LCCN,where the symbols Rn and P∞ quantify the robustness of a network. Normally, the larger the values of Rn and P∞are, the more robust the network is.


## 3. Motivations

Network robustness analysis is involved with network models which specify how cascading failures propagate on complex networks. In this paper, we have proposed two network models to explore the robustness of multipartite networks. The reason for developing new models is that existing models that are well studied for multilayer networks are not amenable to multipartite networks.When exploiting the robustness of multilayer networks, a widely used network model is from [45] which is illustrated in Figure 3. Figure 3 exhibits the dynamic process on a three-layer network with one-to-one correlations, i.e., every node in one subnetwork exactly depends on one node in the other subnetwork. Initially, node 2 of network G1 shown in Figure 3 is attacked. Due to the interdependency, the removal of node 2 leads to the removal of nodes 6 and 10 together with the edges attached to them in step 1. The removal of nodes 6 and 10 further breaks network G2 into two parts. It is assumed that only nodes in the LCC for each subnetwork of a multilayer network will be of interest. Putting it another way, the nodes that are not in the LCC will be regarded as dysfunctional and will be removed. Therefore, in step 2, node 5 together with nodes 1 and 9 (interdependency) is removed. As network G3 fragments into two parts and based on the LCC theory, node 11 or node 12 will be removed (assume that node 11 is removed). Eventually, only nodes 4, 8, and 12 are remained.Figure 3
Network model for depicting the cascading failures of a multilayer network subject to node attacks. NetworksG1, G2, and G3 are with one-to-one correlations. (a) Node 2 of network G1 is originally attacked. (b) The failure of node 2 leads to the failures of nodes 6 and 10 due to interdependency. (c) The model posits that, for each network, only nodes in the LCC will be considered as functional, and therefore, nodes 1, 5, and 9 are removed. (d) As a consequence, the failure of node 2 eventually leads to the existence of only three nodes (4, 8, and 12 or 3, 7, and 11).In the literature, there are several variants [21, 83–85] of the model shown in Figure 3. However, those models cannot be applied to multipartite networks. The reason is apparent because in those models the focal multilayer network is one-to-one correlated. As we can see from Figure 1 that a multipartite network could be regarded as a special case of a multilayer network with one-to-many correlations.In order to circumvent the deficiency of the model shown in Figure3 so as to better characterize real-world networks, Shao et al. and Dong et al. [55, 86] proposed a model exhibited in Figure 4 for analyzing the robustness of multilayer networks with one-to-many correlations. In Figure 4, a node which has no connections with nodes from its coupled network is regarded as a dysfunctional node. Within a network, nodes that are not in the LCC will also be regarded as dysfunctional nodes. Cascading failures will continue on the network until no further failure is possible.Figure 4
Network model for depicting the cascading failures on a two-layer network (networks A and B) with one-to-many correlations. The directed links are support links. The arrows point from the support nodes to the dependent nodes. (a) Nodes A1 and B6 are initially attacked. (b) Cascading failures on network A. Node A2 is removed because it is disconnected from network A. Node A7 is removed due to the lack of support. The removal of A7 further leads to the failure of node A6 as it is disconnected. (c) Cascading failures on network B. Nodes B1, B2, and B7 are removed as they have no supports. Node B3 is removed as it is disconnected from network B. (d) The LCC of the focal network in the final stable stage.
(a)
(b)
(c)
(d)This model displayed in Figure4 seems very promising for multipartite networks if we neglect the directions of the edges. However, this model is still not applicable to multipartite networks. The reason is that this model shares the same idea with the model presented in Figure 3. More specifically, they consider the LCC for each layer of a multilayer network as each single layer is an independent subnetwork which has its own network structure. By contrast, each “layer” of a multipartite network is not an independent subnetwork as nodes in each “layer” are disconnected from each other. For the models surveyed in Figures 3 and 4, they could determine the LCC of each layer of a multilayer network without considering any other layers. However, one could not determine the LCC of each “layer” of a multipartite network without considering any other “layers.”In this paper, we first develop two network models for multipartite networks. Based on the developed models, we then adopt the simulation-based method instead of theoretical methods, especially those represented by percolation theories, to plumb the robustness of multipartite network. The main reason is that existing models for multilayer networks are not amenable to multipartite networks which directly elicits the infeasibility of the applications of the corresponding theoretical methods to multipartite networks, since those theoretical methods are developed based on the corresponding network models.


## 4. Methodology

### 4.1. Framework of Robustness Evaluation Method

For a givenL-partite network G, we define ni=Vi as the number of nodes in partite set Vi. We utilize Algorithm 1 to evaluate its robustness under target node attacks.Algorithm 1:Framework of the method for analyzing the robustness of an L-partite network under target node attacks.
Input: anL-partite network G; index i∈1,L
Output: the robustness curves
(1)
ImplementPj∞= for all j∈1,L; //memory allocation
(2)
V
i
r
=
NodeRanking
V
i
,
centrality
,
descend; //see Section 4.4.
(3)
For
p
=
0
:
interval
:
1
do
(a)
Gr=NodeRemoveG,Vir1:1−pni; //remove the former 1−pni nodes from Vir.
(b)
Gr⟵CascadingFailureGr,model; //see Sections 4.2 and 4.3.
(c)
LCC=LargestConnectedComponentGr;
(d)
ImplementPj∞⟵Vj∩LCC/nj for all j∈1,L; //in the final LCC, calculate the fraction of nodes remained in each node set.
(4)
End
(5)
Go to step 2 and repeat the above processes forT times. Calculate the average values of Pj∞.
(6)
PlotPj∞ with respect to p.In step 2 of Algorithm1, for a given centrality metric, we sort the nodes in Vi in a descend order based on their centralities. In case one needs to analyze the robustness of an L-partite network under target node attacks that occur to every partite set, then the three variables, i.e., Vir, Vi, and ni, as given in Algorithm 1 should be replaced as Vr, V, and N, respectively.


### 4.2. Proposed Model M1 for Multipartite Networks

We have illustrated in Section3 that existing network models are not applicable to analyze the robustness of multipartite networks due to the special structure of multipartite networks. With regard to this, here we first propose network model M1 for multipartite networks.Figure5 describes our proposed model M1 for robustness analysis of multipartite networks. For the tripartite network displayed in Figure 5, node 2 is initially attacked. Model M1 takes a multipartite network as a whole. Model M1 cares about the LCC of a multipartite network after node attacks happened. In step 1, the removal of node 2 breaks the whole network into two parts. Based on the LCC concept, in step 2, all the nodes in red will be removed, and in the end, only the nodes that belong to the LCC of the focal multipartite network are remained.Figure 5
Proposed model M1 for depicting the cascading failures of a multipartite network subject to node attacks. (a) Initially, node 2 of partite setV1 is attacked. (b) The removal of node 2 breaks the focal multipartite network into two parts. (c) The model M1 assumes that only nodes in the LCC survive the attack, and therefore, the nodes marked in red will be removed. (d) Eventually, nodes 3, 4, 7, 8, 11, and 12 are remained.


### 4.3. Proposed Model M2 for Multipartite Networks

Model M1 treats a multipartite network as a whole. Model M1 is straightforward and simple since it shares the basic idea with the model that is widely utilized for analyzing the robustness of single-layer networks. Inspired by the existing models established for analyzing the robustness of multilayer networks [16], here we put forward another model, i.e., M2, to describe the dynamic process of multipartite networks to perturbations. Different to model M1, model M2 considers the LCC of each bipartite network contained in a multipartite network. Model M2 eventually calculates the LCC that contains nodes from every partite set of a multipartite network.Model M2 works in a bounce-forward-and-back manner and assumes that only nodes in the LCC are of concern. Given anL-partite network with Vi being its i-th partite set. Assume that nodes from Vi for i∈1,L−1 are under attack. Then, model M2 first works in a bounce-forward way. Specifically, model M2 first analyzes the LCC of the bipartite network composed of partite sets Vi and Vi+1 and the edges between them. In the next step, model M2 moves to analyze the bipartite network that contains partite sets Vi+1 and Vi+2. The above process moves forward until the bipartite network that contains partite sets VL−1 and VL is reached and its LCC is identified. Then, model M2 starts to work in a bounce-back manner. Specifically, model M2 analyzes the LCC of the bipartite network composed of partite sets VL−2 and VL−1 and the edges between them. Then, model M2 moves to analyze the bipartite network that contains partite sets VL−3 and VL−2 and the bounce-back process continues until the bipartite network that contains partite sets V1 and V2 is reached and the new start of the bounce-forward process is initiated. The aforementioned bounce-forward-and-back process repeats until a stable stage is reached in which no node and edge removals are possible. The remaining part of the network is then the LCC that model M2 aims to figure out. Note that in the case where nodes from Vi for i=L are under attack, then model M2 first implements the bounce-back procedure.Figure6 takes the same multipartite network shown in Figure 5 as an example to explain in detail how model M2 works. Initially, node 2 is attacked. The removal of node 2 breaks the bipartite network consisting of nodes in V1 and V2 into three parts, i.e., {1, 5, 6}, {3, 7}, and {4, 8}. As mentioned earlier, model M2 considers the LCC of each bipartite network contained in a multipartite network, therefore nodes 3, 4, 7, and 8 will be removed in step 1 since they are not in the LCC of the bipartite network. Analogously, in step 2, the nodes that are not in the LCC of the second bipartite network are removed, and eventually, only nodes 1, 6, and 10 survive (also could be nodes 1, 5, and 9).Figure 6
Proposed model M2 for depicting the cascading failures of a multipartite network subject to node attacks. (a) Initially, node 2 of partite setV1 is attacked. (b) The removal of node 2 fragments the bipartite network containing partite sets V1 and V2 and nodes outside the LCC will be removed. (c) The removal of nodes 7 and 8 fragments the bipartite network containing partite sets V2 and V3 and nodes outside the LCC will be removed. (d) Eventually, only nodes 1, 6, and 10 (or 1, 5, and 9) survive the attack of node 2.


### 4.4. Node Centrality Metrics

Note that, for real-world complex networks, nodes with higher significance have higher probabilities to be attacked. When investigating the robustness of multipartite networks under target node attacks, one therefore may wish to rank the nodes of a multipartite network based on their significance such that one can choose the nodes to be removed. In network science domain, centrality metrics have been widely used to measure the significance of the nodes in a network. In the literature, there are a handful of node centrality metrics [87]. In this paper, we only choose eight of them. On the one hand, the adopted metrics are widely investigated in the literature. On the other hand, they are computationally friendly. The adopted centrality metrics are described below.


#### 4.4.1. Degree Centrality

The Degree centrality of nodei is calculated as follows:(4)Cdegi=di=∑j=1Naij.


#### 4.4.2. Betweenness Centrality

The Betweenness centrality of nodei is calculated as follows:(5)Cbtwi=∑s≠i∑t≠ipstipst,where pst denotes the number of shortest paths from two different nodes s and t in G and psti represents the number of paths in pst that have passed through node i.


#### 4.4.3. Closeness Centrality

The Closeness centrality of nodei is measured as follows:(6)Cclsi=N−1∑j≠idisij,where disij denotes the geodesic distance between nodes i and j.


#### 4.4.4. EigenVector Centrality

The EigenVector centrality of nodei is figured out by solving the following equation:(7)x→=cAx→,where vector x→=Ceig1,Ceig2,…,CeigN and c is a proportionality constant which is generally set to c=1/λ with λ being the largest eigenvalue of A.


#### 4.4.5. Coreness Centrality

The Coreness centrality of nodei is figured out by implementing the k-shell [88, 89] decomposition of G and Ccori=k for all the nodes in the k-shell.


#### 4.4.6. Subgraph Centrality

The Subgraph centrality of nodei is calculated as follows:(8)Csbgi=∑α=1∞Aαiiα!,where Aαii stands for the diagonal element of the αth power of A.


#### 4.4.7. PageRank Centrality

The PageRank centrality of nodei at step τ is calculated as follows:(9)Cpgriτ=∑j=1NaijCpgrjτ−1kjout+1N1−β,where β is a random jumping probability and is set to β=0.85 in this study. The above process will stop once a steady state is reached and all the Cpgri values are obtained.


#### 4.4.8. LocalRank Centrality

The LocalRank centrality of nodei is calculated as follows:(10)Clcri=∑j∈Ni∑t∈NjRt,where Ni denotes the neighbouring nodes of node i and Rt represents the number of node t’s neighbours and their neighbours’ neighbours.


## 4.1. Framework of Robustness Evaluation Method

For a givenL-partite network G, we define ni=Vi as the number of nodes in partite set Vi. We utilize Algorithm 1 to evaluate its robustness under target node attacks.Algorithm 1:Framework of the method for analyzing the robustness of an L-partite network under target node attacks.
Input: anL-partite network G; index i∈1,L
Output: the robustness curves
(1)
ImplementPj∞= for all j∈1,L; //memory allocation
(2)
V
i
r
=
NodeRanking
V
i
,
centrality
,
descend; //see Section 4.4.
(3)
For
p
=
0
:
interval
:
1
do
(a)
Gr=NodeRemoveG,Vir1:1−pni; //remove the former 1−pni nodes from Vir.
(b)
Gr⟵CascadingFailureGr,model; //see Sections 4.2 and 4.3.
(c)
LCC=LargestConnectedComponentGr;
(d)
ImplementPj∞⟵Vj∩LCC/nj for all j∈1,L; //in the final LCC, calculate the fraction of nodes remained in each node set.
(4)
End
(5)
Go to step 2 and repeat the above processes forT times. Calculate the average values of Pj∞.
(6)
PlotPj∞ with respect to p.In step 2 of Algorithm1, for a given centrality metric, we sort the nodes in Vi in a descend order based on their centralities. In case one needs to analyze the robustness of an L-partite network under target node attacks that occur to every partite set, then the three variables, i.e., Vir, Vi, and ni, as given in Algorithm 1 should be replaced as Vr, V, and N, respectively.


## 4.2. Proposed Model M1 for Multipartite Networks

We have illustrated in Section3 that existing network models are not applicable to analyze the robustness of multipartite networks due to the special structure of multipartite networks. With regard to this, here we first propose network model M1 for multipartite networks.Figure5 describes our proposed model M1 for robustness analysis of multipartite networks. For the tripartite network displayed in Figure 5, node 2 is initially attacked. Model M1 takes a multipartite network as a whole. Model M1 cares about the LCC of a multipartite network after node attacks happened. In step 1, the removal of node 2 breaks the whole network into two parts. Based on the LCC concept, in step 2, all the nodes in red will be removed, and in the end, only the nodes that belong to the LCC of the focal multipartite network are remained.Figure 5
Proposed model M1 for depicting the cascading failures of a multipartite network subject to node attacks. (a) Initially, node 2 of partite setV1 is attacked. (b) The removal of node 2 breaks the focal multipartite network into two parts. (c) The model M1 assumes that only nodes in the LCC survive the attack, and therefore, the nodes marked in red will be removed. (d) Eventually, nodes 3, 4, 7, 8, 11, and 12 are remained.


## 4.3. Proposed Model M2 for Multipartite Networks

Model M1 treats a multipartite network as a whole. Model M1 is straightforward and simple since it shares the basic idea with the model that is widely utilized for analyzing the robustness of single-layer networks. Inspired by the existing models established for analyzing the robustness of multilayer networks [16], here we put forward another model, i.e., M2, to describe the dynamic process of multipartite networks to perturbations. Different to model M1, model M2 considers the LCC of each bipartite network contained in a multipartite network. Model M2 eventually calculates the LCC that contains nodes from every partite set of a multipartite network.Model M2 works in a bounce-forward-and-back manner and assumes that only nodes in the LCC are of concern. Given anL-partite network with Vi being its i-th partite set. Assume that nodes from Vi for i∈1,L−1 are under attack. Then, model M2 first works in a bounce-forward way. Specifically, model M2 first analyzes the LCC of the bipartite network composed of partite sets Vi and Vi+1 and the edges between them. In the next step, model M2 moves to analyze the bipartite network that contains partite sets Vi+1 and Vi+2. The above process moves forward until the bipartite network that contains partite sets VL−1 and VL is reached and its LCC is identified. Then, model M2 starts to work in a bounce-back manner. Specifically, model M2 analyzes the LCC of the bipartite network composed of partite sets VL−2 and VL−1 and the edges between them. Then, model M2 moves to analyze the bipartite network that contains partite sets VL−3 and VL−2 and the bounce-back process continues until the bipartite network that contains partite sets V1 and V2 is reached and the new start of the bounce-forward process is initiated. The aforementioned bounce-forward-and-back process repeats until a stable stage is reached in which no node and edge removals are possible. The remaining part of the network is then the LCC that model M2 aims to figure out. Note that in the case where nodes from Vi for i=L are under attack, then model M2 first implements the bounce-back procedure.Figure6 takes the same multipartite network shown in Figure 5 as an example to explain in detail how model M2 works. Initially, node 2 is attacked. The removal of node 2 breaks the bipartite network consisting of nodes in V1 and V2 into three parts, i.e., {1, 5, 6}, {3, 7}, and {4, 8}. As mentioned earlier, model M2 considers the LCC of each bipartite network contained in a multipartite network, therefore nodes 3, 4, 7, and 8 will be removed in step 1 since they are not in the LCC of the bipartite network. Analogously, in step 2, the nodes that are not in the LCC of the second bipartite network are removed, and eventually, only nodes 1, 6, and 10 survive (also could be nodes 1, 5, and 9).Figure 6
Proposed model M2 for depicting the cascading failures of a multipartite network subject to node attacks. (a) Initially, node 2 of partite setV1 is attacked. (b) The removal of node 2 fragments the bipartite network containing partite sets V1 and V2 and nodes outside the LCC will be removed. (c) The removal of nodes 7 and 8 fragments the bipartite network containing partite sets V2 and V3 and nodes outside the LCC will be removed. (d) Eventually, only nodes 1, 6, and 10 (or 1, 5, and 9) survive the attack of node 2.


## 4.4. Node Centrality Metrics

Note that, for real-world complex networks, nodes with higher significance have higher probabilities to be attacked. When investigating the robustness of multipartite networks under target node attacks, one therefore may wish to rank the nodes of a multipartite network based on their significance such that one can choose the nodes to be removed. In network science domain, centrality metrics have been widely used to measure the significance of the nodes in a network. In the literature, there are a handful of node centrality metrics [87]. In this paper, we only choose eight of them. On the one hand, the adopted metrics are widely investigated in the literature. On the other hand, they are computationally friendly. The adopted centrality metrics are described below.


### 4.4.1. Degree Centrality

The Degree centrality of nodei is calculated as follows:(4)Cdegi=di=∑j=1Naij.


### 4.4.2. Betweenness Centrality

The Betweenness centrality of nodei is calculated as follows:(5)Cbtwi=∑s≠i∑t≠ipstipst,where pst denotes the number of shortest paths from two different nodes s and t in G and psti represents the number of paths in pst that have passed through node i.


### 4.4.3. Closeness Centrality

The Closeness centrality of nodei is measured as follows:(6)Cclsi=N−1∑j≠idisij,where disij denotes the geodesic distance between nodes i and j.


### 4.4.4. EigenVector Centrality

The EigenVector centrality of nodei is figured out by solving the following equation:(7)x→=cAx→,where vector x→=Ceig1,Ceig2,…,CeigN and c is a proportionality constant which is generally set to c=1/λ with λ being the largest eigenvalue of A.


### 4.4.5. Coreness Centrality

The Coreness centrality of nodei is figured out by implementing the k-shell [88, 89] decomposition of G and Ccori=k for all the nodes in the k-shell.


### 4.4.6. Subgraph Centrality

The Subgraph centrality of nodei is calculated as follows:(8)Csbgi=∑α=1∞Aαiiα!,where Aαii stands for the diagonal element of the αth power of A.


### 4.4.7. PageRank Centrality

The PageRank centrality of nodei at step τ is calculated as follows:(9)Cpgriτ=∑j=1NaijCpgrjτ−1kjout+1N1−β,where β is a random jumping probability and is set to β=0.85 in this study. The above process will stop once a steady state is reached and all the Cpgri values are obtained.


### 4.4.8. LocalRank Centrality

The LocalRank centrality of nodei is calculated as follows:(10)Clcri=∑j∈Ni∑t∈NjRt,where Ni denotes the neighbouring nodes of node i and Rt represents the number of node t’s neighbours and their neighbours’ neighbours.


## 4.4.1. Degree Centrality

The Degree centrality of nodei is calculated as follows:(4)Cdegi=di=∑j=1Naij.


## 4.4.2. Betweenness Centrality

The Betweenness centrality of nodei is calculated as follows:(5)Cbtwi=∑s≠i∑t≠ipstipst,where pst denotes the number of shortest paths from two different nodes s and t in G and psti represents the number of paths in pst that have passed through node i.


## 4.4.3. Closeness Centrality

The Closeness centrality of nodei is measured as follows:(6)Cclsi=N−1∑j≠idisij,where disij denotes the geodesic distance between nodes i and j.


## 4.4.4. EigenVector Centrality

The EigenVector centrality of nodei is figured out by solving the following equation:(7)x→=cAx→,where vector x→=Ceig1,Ceig2,…,CeigN and c is a proportionality constant which is generally set to c=1/λ with λ being the largest eigenvalue of A.


## 4.4.5. Coreness Centrality

The Coreness centrality of nodei is figured out by implementing the k-shell [88, 89] decomposition of G and Ccori=k for all the nodes in the k-shell.


## 4.4.6. Subgraph Centrality

The Subgraph centrality of nodei is calculated as follows:(8)Csbgi=∑α=1∞Aαiiα!,where Aαii stands for the diagonal element of the αth power of A.


## 4.4.7. PageRank Centrality

The PageRank centrality of nodei at step τ is calculated as follows:(9)Cpgriτ=∑j=1NaijCpgrjτ−1kjout+1N1−β,where β is a random jumping probability and is set to β=0.85 in this study. The above process will stop once a steady state is reached and all the Cpgri values are obtained.


## 4.4.8. LocalRank Centrality

The LocalRank centrality of nodei is calculated as follows:(10)Clcri=∑j∈Ni∑t∈NjRt,where Ni denotes the neighbouring nodes of node i and Rt represents the number of node t’s neighbours and their neighbours’ neighbours.


## 5. Simulations

### 5.1. Experimental Settings

For the sake of testing purpose, in the experiments we generate multipartite networks with controllable Poisson degree distributions. Let us define a probability vectorp⟶=p1,p2,…,pL−1. Then, we generate an L-partite network with N=∑ni nodes by connecting each node a∈Vi with each node b∈Vi+1 with the probability pi for all i∈1,L−1.It is easy to figure out that the degree distributionPi,i+1k of the nodes in Vi that have connections with nodes in Vi+1 follows the Poisson distribution which can be formulated as(11)Pi,i+1k≈e−ki,i+1ki,i+1kk!,with its mean degree ki,i+1=ni+1pi. Analogously, it is easy to get(12)Pi+1,ik≈e−ki+1,iki+1,ikk!,with the corresponding mean degree ki+1,i=nipi.In the simulations, without loss of generality, we generate a tripartite networkG1 with its parameter settings being given as follows: n1,n2,n3=1.5,1.5,1×105, p⟶=6/n1+n2,4/n3+n2. During the simulations, the settings of the parameters interval and T as presented in Algorithm 1 are interval=0.04 and T=100. We also generate G1 for 5 times. Therefore, all the results are averaged over 500 times.


### 5.2. Robustness Based on Network Model M1

For a tripartite networkG1, we, respectively, investigate its robustness under three different cases, i.e., the case that the node removal happens to the first partite set V1, the case that the node removal happens to the second partite set V2, and the case that the node removal happens to every partite set. We first calculate the centralities of the nodes in G1 given a specific centrality metric. For each case scenario, we then sort the corresponding nodes in a descend order. Afterward, for a given value of p, we remove the former 1−p fraction of nodes from the corresponding node set. We then let the cascading failures propagate with respect to model M1. When G1 reaches a stable state where no node and edge removals are possible, we calculate the values of Pi∞ and P∞. The simulation results are exhibited in Figure 7.Figure 7
Model M1-based robustness of tripartite networkG1 subject to target node attacks. The fractions Pi∞, i.e., fractions of nodes in Vi⊂G1 that also belong to the LCC, are drawn with respect to different values of p. (a–c) the case where the node attacks occur to V1. (d–f) the case where the node attacks occur to V2. (g–i) the case where the node attacks occur to the whole network.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Note that an important indicator for network robustness analysis is the critical pointpc of p at which the value of Pi∞ starts to change from a small value close to zero to a relatively large value. The smaller the value of pc is, the more robust the network is. We can clearly see from Figures 7(a)–7(c) that pc=0, which indicates that the studied multipartite networks are extremely robust to target attacks if the node attacks only occur to V1. Figures 7(d)–7(f) show that the values of pc are approximately in the range pc∈0.2,0.36, while Figures 7(g)–7(i) indicate that the values of pc are approximately in the range pc∈0.4,0.7.The results recorded in Figure7 suggest that the robustness of multipartite networks based on the network model M1 presents a continuous phase transition phenomenon, which indicates that multipartite networks are robust when model M1 is considered. As for the eight investigated node centrality metrics, we can see from Figures 7(a)–7(f) that the robustness curves are close to each other when the attacks only happen to one partite set, which indicates that their impacts on the networks’ robustness are not significant. When the attacks happen to every partite set of a multipartite network, we can see from Figures 7(g)–7(i) that a multipartite network is relatively more fragile with respect to the Degree and PageRank centralities. By observing Figure 7, we also notice that the EigenVector centrality has the least impact on the robustness of multipartite networks to target node attacks.


### 5.3. Robustness Based on Network Model M2

Analogous to what are done in the above subsection, we here study the robustness of tripartite networkG1 subject to target node attacks with respect to the network model M2. Figure 8 presents the simulation results.Figure 8
Model M2-based robustness of tripartite networkG1 subject to target node attacks. The fractions Pi∞, i.e., fractions of nodes in Vi⊂G1 that also belong to the LCC, are drawn with respect to different values of p. (a–c) the case where the node attacks occur to V1. (d–f) the case where the node attacks occur to V2. (g–i) the case where the node attacks occur to the whole network.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)It can be observed from the robustness curves drawn in Figure8 that there exist drastic jumps of the values of Pi∞, i.e., at the critical points of pc, the values of Pi∞ suddenly change from some small values close to zero to some large values. The results shown in Figures 8(a)–8(c) indicate that even small scale attacks could break down the studied multipartite networks. The values of pc as recorded in Figure 8 are relatively larger than those recorded in Figure 7. Different to what are shown in Figure 7, the values of pc do not vary too much with regard to the three node attack strategies. The results shown in Figure 8 display discontinuous phase transition, which indicates that multipartite networks are extremely vulnerable in the face of target attacks when the network model M2 is considered.As for the eight investigated node centrality metrics, the experiments demonstrated in Figures8(g)–8(i) indicate that if the node attacks occur to every partite set, their impacts on the robustness of multipartite networks are tinny as the curves are very close to each other, which is different from the phenomenon observed in Figure 7. Meanwhile, we notice from Figure 8 that the Coreness centrality has the least impact on the robustness of multipartite networks to target node attacks when model M2 is considered. Moreover, a multipartite network is relatively more vulnerable with respect to the Degree and LocalRank centralities.


### 5.4. Discussion on Network Robustness

The above experiments onL-partite networks are carried out in the case of L=3. One may argue the generalization of the robustness phenomena observed from the above experiments. With regard to this, here we carry out experiments for the case of L>3. As indicated by the above experiments that the effects of the eight centrality metrics on the network robustness are not so significant, here we therefore choose the Degree centrality for testing purpose.Figure9 demonstrates the robustness experiments on four multipartite networks whose sizes are controlled by the parameter L. It can be seen from Figure 9 that the impacts of L on the robustness of multipartite networks with respect to network models M1 and M2 are not significant since the robustness curves are close to each other. In the literature, it has been reported that the robustness of multilayer networks decreases sharply with the increase of L [14]. However, by contrast, Figure 9 indicates that the robustness of multipartite networks with respect to network models M1 and M2 does not change sharply with respect to L. Surprisingly, the robustness curves recorded in Figure 9 indicate that the robustness of multipartite networks increases with the increase of L.Figure 9
Impacts ofL on the robustness of multipartite networks (size controlled by L) each of which is subject to node attacks occurred to every partite set. For each network, we set ni=nj=4×104 and pi=pj=6/ni. (a) Robustness of multipartite networks based on the network model M1. (b) Robustness of multipartite networks based on the network model M2.
(a)
(b)One may observe from Figure9(b) that the robustness curves show some bumps for p∈0.3,0.5. The bumps are caused by the relatively small number of experimental trials which is set to be 500. For a given multipartite network with L node sets, in the experiments we set ni=nj=4×104 for all i,j∈1,L. For L=4, we can see from Figure 9(b) that the robustness curve does not show any bump. With the increase of L, the generated L-partite networks are becoming larger, while the number of experimental trials is fixed to be 500. The larger the size of an L-partite network, the larger the size of the corresponding bump, and this is what has been reflected in Figure 9(b). The bumps will disappear with the increase of the number of experimental trials.In the above experiments, we have fixedpi and pj, i.e., the degree of nodes in each partite set is fixed. Here, we investigate the impacts of degree on the robustness of multipartite networks. For simplicity and without loss of generality, we in the experiments study the case of L=3. Figure 10 exhibits the impact of degree on the robustness of a tripartite network. Figure 10 apparently demonstrates the continuous and discontinuous phase transition phenomena on the robustness of multipartite networks. The robustness curves drawn in Figure 10 indicate that the larger the degree of a multipartite network is, the more robust the network is in face of target attacks.Figure 10
Impacts of degree on the robustness of a tripartite network subject to node attacks to every partite set. The network configurations areni=nj=4×104 and pi=pj=d/2ni. (a) Robustness of the tripartite network based on the network model M1. (b) Robustness of the tripartite network based on the network model M2.
(a)
(b)


### 5.5. Discussion on Percolation Theories

Note that this paper adopts the empirical method to investigate the robustness of multipartite networks. The motivation has been clarified in Section3. Based on the assertion that a multipartite network is practically a simple case of a multilayer network, one therefore may argue that existing percolation theories for analyzing the robustness of multilayer networks could be applied to multipartite networks. Here, we will prove that this idea is not working.One could see from Figure5 that the network model M1 practically regards a multipartite network as a whole. Therefore, if the node attacks occur to every partite set of a multipartite network, then percolation theory for single-layer networks [3] might be possible for analyzing the robustness of multipartite networks. As the majority of existing percolation theories for analyzing the robustness of networks deal with random node attack scenarios, in the following we only pay attention to network robustness under random node attacks.Given a single-layer networkG, let Pk be its degree distribution. When we randomly remove 1−p fraction of nodes from G, the remaining fraction of nodes in the LCC can be mathematically calculated as follows:(13)P∞=p1−G0u,where G0u=∑k=0∞Pkuk is the generating function of Pk. The variable u is calculated as follows:(14)u=1−p+pG1u,where G1u=G0′u/G0′1 is the excess generating function of Pk with G0′u being the first-order derivative of G0u.For anL-partite network G1 generated in the way shown in this paper, we can easily work out the degree distribution Pik for the nodes in Vi as follows:(15)Pik=naqpaq1−pana−qnbk−qpbk−q1−pbnb−k+q≈kikk!⋅e−ki,where ki=ki,a+ki,b and a=i−1 and b=i+1.Based on the above equation, we can further figure out the degree distributionPk of G1 as follows:(16)Pk≈∑i=1LniNPik.In compliance with the percolation theory formulated in equations (13) and (14), we can have the following simplified formula for multipartite networks:(17)P∞=p1−∑i=1LniNG0iu=p1−∑i=1LniNekiu−1,(18)u=1−p+pG1u=1−p+p∑i=1LG0i′uG0i′1=1−p+p∑i=1LniNekiu−1,where we have made use of the following expression to simplify the above derivations:(19)G0iu=∑k=0∞Pikuk=∑k=0∞kikk!e−kiuk=ekiu−1.In what follows, we will check the correctness of equations (17) and (18) through experiments on multipartite networks. To do so, we generate four multipartite networks G1, G2, G3, and G4. For the four networks, we fix pi=pj=d/2ni, ni=nj=4×104, and d=6. We, respectively, set L=2, L=3, L=4, and L=5 for G1, G2, G3, and G4.Figure11(a) exhibits the simulation results on the robustness of networks G1, G2, G3, and G4 as well as the theoretical results obtained by solving equations (17) and (18) It can be seen from Figure 11(a) that the simulation results coincide well with the theoretical results.Figure 11
Validation of the correctness of the application of existing percolation theory for single-layer networks to multipartite networks. (a) Simulations on multipartite networks where each multipartite network has equal number of nodes for each partite set. (b) Simulations on bipartite networks where the number of nodes for each partite set of the focal network is controlled by parameterα.
(a)
(b)Note that the theoretical results shown in Figure11(a) are obtained based on two conditions, i.e., ni=nj and node failures occur to every partite set of the focal network. To further check the correctness of equations (17) and (18), we investigate the condition where ni≠nj. Specifically, for network G1, we introduce parameter α to control the number of nodes for its two node sets, i.e., we set α=n1/n1+n2. We fix N=4×104 for G1, and we test the correctness of equations (17) and (18) for α=1/8,2/8,4/8. The corresponding experiments are presented in Figure 11(b). We can clearly see from Figure 11(b) that the theoretical results obtained by equations (17) and (18) do not comply with the simulation results if ni≠nj. We conclude that the existing percolation theory for single-layer networks only applies to multipartite networks where the focal multipartite network has equal number of nodes for each partite set and the node failures occur to every partite set.As for the network model M2, the robustness analysis of multipartite networks based on model M2 shares something in common with the work presented in [55]. Let us consider a multipartite network G1 with L=3 and ni=nj. If we take the bipartite network consisting of partite sets V3 and V2 as a whole, then network G1 therefore could be regarded as a special multilayer network that is similar to the network model investigated in [55]. One thus might argue that the percolation theory developed in [55] could be applicable to multipartite networks.Given a two-layer network (consisting of networks A and B) as discussed in [55], when randomly removing 1−pA and 1−pB fractions of nodes, respectively, from A and B, the corresponding percolation theory is formulated as follows:(20)fA=G1A1−uA1−fA,fB=G1B1−uB1−fB,uA=pA1−G0A˜1−PB∞,uB=pB1−G0B˜1−PA∞,PA∞=uA1−G0A1−uA1−fA,PB∞=uB1−G0B1−uB1−fB,where fA, fB, uA, and uB are four unknowns; G0A˜, G0B˜, G0A, and G0B are, respectively, the generating functions of PA˜k, PB˜k, PAk, and PBk.In the above equation,PA˜k denotes the interlayer degree distribution, while PAk denotes the intralayer degree distribution. Suppose that the percolation theory presented in equation (20) is applicable to multipartite networks, then when we randomly remove 1−p fraction of nodes from V1⊂G1, the robustness of G1 should be mathematically calculated as follows:(21)fA=0,fB=G1B1−uB1−fB,uA=p1−G0A˜1−PB∞,uB=1−G0B˜1−PA∞,PA∞=uA,PB∞=uB1−G0B1−uB1−fB..We generate networkG1 with the parameter configurations given as n1=n2=n3=4×104, p1=p2=d/2n1, and d=6,8,10. For the generated network G1, by substituting its corresponding degree distributions to the above equation, we then could figure out the solutions to PA∞ and PB∞ by numerically solving the following equations:(22)PA∞=p1−e−d/2PB∞,PB∞=1−e−d/2PA∞1−e−d/2PB∞.Figure12 exhibits the simulation results on the robustness of networks G1 as well as the theoretical results obtained by solving equation (21). We get P∞ through expression P∞=PA∞+2PB∞/3. It can be clearly seen from Figure 12 that the theory does not apply to multipartite networks.Figure 12
Validation of the correctness of the application of existing percolation theory for multilayer networks to multipartite networks.


## 5.1. Experimental Settings

For the sake of testing purpose, in the experiments we generate multipartite networks with controllable Poisson degree distributions. Let us define a probability vectorp⟶=p1,p2,…,pL−1. Then, we generate an L-partite network with N=∑ni nodes by connecting each node a∈Vi with each node b∈Vi+1 with the probability pi for all i∈1,L−1.It is easy to figure out that the degree distributionPi,i+1k of the nodes in Vi that have connections with nodes in Vi+1 follows the Poisson distribution which can be formulated as(11)Pi,i+1k≈e−ki,i+1ki,i+1kk!,with its mean degree ki,i+1=ni+1pi. Analogously, it is easy to get(12)Pi+1,ik≈e−ki+1,iki+1,ikk!,with the corresponding mean degree ki+1,i=nipi.In the simulations, without loss of generality, we generate a tripartite networkG1 with its parameter settings being given as follows: n1,n2,n3=1.5,1.5,1×105, p⟶=6/n1+n2,4/n3+n2. During the simulations, the settings of the parameters interval and T as presented in Algorithm 1 are interval=0.04 and T=100. We also generate G1 for 5 times. Therefore, all the results are averaged over 500 times.


## 5.2. Robustness Based on Network Model M1

For a tripartite networkG1, we, respectively, investigate its robustness under three different cases, i.e., the case that the node removal happens to the first partite set V1, the case that the node removal happens to the second partite set V2, and the case that the node removal happens to every partite set. We first calculate the centralities of the nodes in G1 given a specific centrality metric. For each case scenario, we then sort the corresponding nodes in a descend order. Afterward, for a given value of p, we remove the former 1−p fraction of nodes from the corresponding node set. We then let the cascading failures propagate with respect to model M1. When G1 reaches a stable state where no node and edge removals are possible, we calculate the values of Pi∞ and P∞. The simulation results are exhibited in Figure 7.Figure 7
Model M1-based robustness of tripartite networkG1 subject to target node attacks. The fractions Pi∞, i.e., fractions of nodes in Vi⊂G1 that also belong to the LCC, are drawn with respect to different values of p. (a–c) the case where the node attacks occur to V1. (d–f) the case where the node attacks occur to V2. (g–i) the case where the node attacks occur to the whole network.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)Note that an important indicator for network robustness analysis is the critical pointpc of p at which the value of Pi∞ starts to change from a small value close to zero to a relatively large value. The smaller the value of pc is, the more robust the network is. We can clearly see from Figures 7(a)–7(c) that pc=0, which indicates that the studied multipartite networks are extremely robust to target attacks if the node attacks only occur to V1. Figures 7(d)–7(f) show that the values of pc are approximately in the range pc∈0.2,0.36, while Figures 7(g)–7(i) indicate that the values of pc are approximately in the range pc∈0.4,0.7.The results recorded in Figure7 suggest that the robustness of multipartite networks based on the network model M1 presents a continuous phase transition phenomenon, which indicates that multipartite networks are robust when model M1 is considered. As for the eight investigated node centrality metrics, we can see from Figures 7(a)–7(f) that the robustness curves are close to each other when the attacks only happen to one partite set, which indicates that their impacts on the networks’ robustness are not significant. When the attacks happen to every partite set of a multipartite network, we can see from Figures 7(g)–7(i) that a multipartite network is relatively more fragile with respect to the Degree and PageRank centralities. By observing Figure 7, we also notice that the EigenVector centrality has the least impact on the robustness of multipartite networks to target node attacks.


## 5.3. Robustness Based on Network Model M2

Analogous to what are done in the above subsection, we here study the robustness of tripartite networkG1 subject to target node attacks with respect to the network model M2. Figure 8 presents the simulation results.Figure 8
Model M2-based robustness of tripartite networkG1 subject to target node attacks. The fractions Pi∞, i.e., fractions of nodes in Vi⊂G1 that also belong to the LCC, are drawn with respect to different values of p. (a–c) the case where the node attacks occur to V1. (d–f) the case where the node attacks occur to V2. (g–i) the case where the node attacks occur to the whole network.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)It can be observed from the robustness curves drawn in Figure8 that there exist drastic jumps of the values of Pi∞, i.e., at the critical points of pc, the values of Pi∞ suddenly change from some small values close to zero to some large values. The results shown in Figures 8(a)–8(c) indicate that even small scale attacks could break down the studied multipartite networks. The values of pc as recorded in Figure 8 are relatively larger than those recorded in Figure 7. Different to what are shown in Figure 7, the values of pc do not vary too much with regard to the three node attack strategies. The results shown in Figure 8 display discontinuous phase transition, which indicates that multipartite networks are extremely vulnerable in the face of target attacks when the network model M2 is considered.As for the eight investigated node centrality metrics, the experiments demonstrated in Figures8(g)–8(i) indicate that if the node attacks occur to every partite set, their impacts on the robustness of multipartite networks are tinny as the curves are very close to each other, which is different from the phenomenon observed in Figure 7. Meanwhile, we notice from Figure 8 that the Coreness centrality has the least impact on the robustness of multipartite networks to target node attacks when model M2 is considered. Moreover, a multipartite network is relatively more vulnerable with respect to the Degree and LocalRank centralities.


## 5.4. Discussion on Network Robustness

The above experiments onL-partite networks are carried out in the case of L=3. One may argue the generalization of the robustness phenomena observed from the above experiments. With regard to this, here we carry out experiments for the case of L>3. As indicated by the above experiments that the effects of the eight centrality metrics on the network robustness are not so significant, here we therefore choose the Degree centrality for testing purpose.Figure9 demonstrates the robustness experiments on four multipartite networks whose sizes are controlled by the parameter L. It can be seen from Figure 9 that the impacts of L on the robustness of multipartite networks with respect to network models M1 and M2 are not significant since the robustness curves are close to each other. In the literature, it has been reported that the robustness of multilayer networks decreases sharply with the increase of L [14]. However, by contrast, Figure 9 indicates that the robustness of multipartite networks with respect to network models M1 and M2 does not change sharply with respect to L. Surprisingly, the robustness curves recorded in Figure 9 indicate that the robustness of multipartite networks increases with the increase of L.Figure 9
Impacts ofL on the robustness of multipartite networks (size controlled by L) each of which is subject to node attacks occurred to every partite set. For each network, we set ni=nj=4×104 and pi=pj=6/ni. (a) Robustness of multipartite networks based on the network model M1. (b) Robustness of multipartite networks based on the network model M2.
(a)
(b)One may observe from Figure9(b) that the robustness curves show some bumps for p∈0.3,0.5. The bumps are caused by the relatively small number of experimental trials which is set to be 500. For a given multipartite network with L node sets, in the experiments we set ni=nj=4×104 for all i,j∈1,L. For L=4, we can see from Figure 9(b) that the robustness curve does not show any bump. With the increase of L, the generated L-partite networks are becoming larger, while the number of experimental trials is fixed to be 500. The larger the size of an L-partite network, the larger the size of the corresponding bump, and this is what has been reflected in Figure 9(b). The bumps will disappear with the increase of the number of experimental trials.In the above experiments, we have fixedpi and pj, i.e., the degree of nodes in each partite set is fixed. Here, we investigate the impacts of degree on the robustness of multipartite networks. For simplicity and without loss of generality, we in the experiments study the case of L=3. Figure 10 exhibits the impact of degree on the robustness of a tripartite network. Figure 10 apparently demonstrates the continuous and discontinuous phase transition phenomena on the robustness of multipartite networks. The robustness curves drawn in Figure 10 indicate that the larger the degree of a multipartite network is, the more robust the network is in face of target attacks.Figure 10
Impacts of degree on the robustness of a tripartite network subject to node attacks to every partite set. The network configurations areni=nj=4×104 and pi=pj=d/2ni. (a) Robustness of the tripartite network based on the network model M1. (b) Robustness of the tripartite network based on the network model M2.
(a)
(b)


## 5.5. Discussion on Percolation Theories

Note that this paper adopts the empirical method to investigate the robustness of multipartite networks. The motivation has been clarified in Section3. Based on the assertion that a multipartite network is practically a simple case of a multilayer network, one therefore may argue that existing percolation theories for analyzing the robustness of multilayer networks could be applied to multipartite networks. Here, we will prove that this idea is not working.One could see from Figure5 that the network model M1 practically regards a multipartite network as a whole. Therefore, if the node attacks occur to every partite set of a multipartite network, then percolation theory for single-layer networks [3] might be possible for analyzing the robustness of multipartite networks. As the majority of existing percolation theories for analyzing the robustness of networks deal with random node attack scenarios, in the following we only pay attention to network robustness under random node attacks.Given a single-layer networkG, let Pk be its degree distribution. When we randomly remove 1−p fraction of nodes from G, the remaining fraction of nodes in the LCC can be mathematically calculated as follows:(13)P∞=p1−G0u,where G0u=∑k=0∞Pkuk is the generating function of Pk. The variable u is calculated as follows:(14)u=1−p+pG1u,where G1u=G0′u/G0′1 is the excess generating function of Pk with G0′u being the first-order derivative of G0u.For anL-partite network G1 generated in the way shown in this paper, we can easily work out the degree distribution Pik for the nodes in Vi as follows:(15)Pik=naqpaq1−pana−qnbk−qpbk−q1−pbnb−k+q≈kikk!⋅e−ki,where ki=ki,a+ki,b and a=i−1 and b=i+1.Based on the above equation, we can further figure out the degree distributionPk of G1 as follows:(16)Pk≈∑i=1LniNPik.In compliance with the percolation theory formulated in equations (13) and (14), we can have the following simplified formula for multipartite networks:(17)P∞=p1−∑i=1LniNG0iu=p1−∑i=1LniNekiu−1,(18)u=1−p+pG1u=1−p+p∑i=1LG0i′uG0i′1=1−p+p∑i=1LniNekiu−1,where we have made use of the following expression to simplify the above derivations:(19)G0iu=∑k=0∞Pikuk=∑k=0∞kikk!e−kiuk=ekiu−1.In what follows, we will check the correctness of equations (17) and (18) through experiments on multipartite networks. To do so, we generate four multipartite networks G1, G2, G3, and G4. For the four networks, we fix pi=pj=d/2ni, ni=nj=4×104, and d=6. We, respectively, set L=2, L=3, L=4, and L=5 for G1, G2, G3, and G4.Figure11(a) exhibits the simulation results on the robustness of networks G1, G2, G3, and G4 as well as the theoretical results obtained by solving equations (17) and (18) It can be seen from Figure 11(a) that the simulation results coincide well with the theoretical results.Figure 11
Validation of the correctness of the application of existing percolation theory for single-layer networks to multipartite networks. (a) Simulations on multipartite networks where each multipartite network has equal number of nodes for each partite set. (b) Simulations on bipartite networks where the number of nodes for each partite set of the focal network is controlled by parameterα.
(a)
(b)Note that the theoretical results shown in Figure11(a) are obtained based on two conditions, i.e., ni=nj and node failures occur to every partite set of the focal network. To further check the correctness of equations (17) and (18), we investigate the condition where ni≠nj. Specifically, for network G1, we introduce parameter α to control the number of nodes for its two node sets, i.e., we set α=n1/n1+n2. We fix N=4×104 for G1, and we test the correctness of equations (17) and (18) for α=1/8,2/8,4/8. The corresponding experiments are presented in Figure 11(b). We can clearly see from Figure 11(b) that the theoretical results obtained by equations (17) and (18) do not comply with the simulation results if ni≠nj. We conclude that the existing percolation theory for single-layer networks only applies to multipartite networks where the focal multipartite network has equal number of nodes for each partite set and the node failures occur to every partite set.As for the network model M2, the robustness analysis of multipartite networks based on model M2 shares something in common with the work presented in [55]. Let us consider a multipartite network G1 with L=3 and ni=nj. If we take the bipartite network consisting of partite sets V3 and V2 as a whole, then network G1 therefore could be regarded as a special multilayer network that is similar to the network model investigated in [55]. One thus might argue that the percolation theory developed in [55] could be applicable to multipartite networks.Given a two-layer network (consisting of networks A and B) as discussed in [55], when randomly removing 1−pA and 1−pB fractions of nodes, respectively, from A and B, the corresponding percolation theory is formulated as follows:(20)fA=G1A1−uA1−fA,fB=G1B1−uB1−fB,uA=pA1−G0A˜1−PB∞,uB=pB1−G0B˜1−PA∞,PA∞=uA1−G0A1−uA1−fA,PB∞=uB1−G0B1−uB1−fB,where fA, fB, uA, and uB are four unknowns; G0A˜, G0B˜, G0A, and G0B are, respectively, the generating functions of PA˜k, PB˜k, PAk, and PBk.In the above equation,PA˜k denotes the interlayer degree distribution, while PAk denotes the intralayer degree distribution. Suppose that the percolation theory presented in equation (20) is applicable to multipartite networks, then when we randomly remove 1−p fraction of nodes from V1⊂G1, the robustness of G1 should be mathematically calculated as follows:(21)fA=0,fB=G1B1−uB1−fB,uA=p1−G0A˜1−PB∞,uB=1−G0B˜1−PA∞,PA∞=uA,PB∞=uB1−G0B1−uB1−fB..We generate networkG1 with the parameter configurations given as n1=n2=n3=4×104, p1=p2=d/2n1, and d=6,8,10. For the generated network G1, by substituting its corresponding degree distributions to the above equation, we then could figure out the solutions to PA∞ and PB∞ by numerically solving the following equations:(22)PA∞=p1−e−d/2PB∞,PB∞=1−e−d/2PA∞1−e−d/2PB∞.Figure12 exhibits the simulation results on the robustness of networks G1 as well as the theoretical results obtained by solving equation (21). We get P∞ through expression P∞=PA∞+2PB∞/3. It can be clearly seen from Figure 12 that the theory does not apply to multipartite networks.Figure 12
Validation of the correctness of the application of existing percolation theory for multilayer networks to multipartite networks.


## 6. Conclusions

Complementary to existing studies on the robustness of multilayer networks, in this work we investigate the robustness of multipartite networks under target node attacks. To do so, two network models, i.e., M1 and M2, have been developed for describing the dynamic process of a multipartite network subject to node failures. Afterward, for a multipartite network, we rank its nodes with respect to eight node centrality metrics. Then, we remove1−p fraction of the sorted nodes and, respectively, calculate the fraction of nodes in the LCC based on models M1 and M2. Experiments on multipartite networks with Poisson degree distributions reveal that the robustness of multipartite networks with respect to models M1 and M2, respectively, displays continuous and discontinuous phase transitions. Experiments also discover that higher degrees and larger number of node sets of multipartite networks could improve their robustness to target node failures.Percolation theories are well studied for analyzing the robustness of multilayer networks. Because a multipartite network could be regarded as a simple case of an interdependent network with one-to-many correlations, therefore theories developed in [21, 81] might be applicable to multipartite networks. However, in this paper, we have proved that those theories are not feasible for multipartite networks. How to develop theories for analyzing the robustness of multipartite networks is still challenging. We are positive that this work could provide clues for future theories for robustness analysis of multipartite networks.A myriad of real-world networks are reported to be scale-free [90–94]. However, in the experiments, only multipartite networks with mixed Poisson degree distributions are tested. The reason is that sampling multipartite networks with power-law degree distributions still remains a challenging issue [95–97]. Let us cite a bipartite network as an example. Let ki and di, respectively, be the degree of a node in V1 and V2. Therefore, when sampling a bipartite network with power-law distributions, one needs to consider the constraint ∑ki​≡∑di. One more thing is that one needs to consider the graphicality condition [98] when sampling multipartite networks with power-law degree distributions. How to sample multipartite networks with arbitrary degree distributions is also challenging and deserves further in-depth dedications [99–101].The robustness phenomena observed on multipartite networks indicate that multipartite networks are more robust to perturbations than multilayer networks do. Note that this conclusion is drawn based on the established models M1 and M2 which are based on the largest connected component theory. During the robustness analysis, the models assume that nodes outside the largest connected component will be dysfunctional and removed. For some real-world complex networks, nodes outside the largest connected components will still be functioning, and models M1 and M2 therefore may not be applicable to such real-world multipartite networks. However, the findings of this work still provide a new thinking towards the robust structure design of complex systems.



---

*Source: 2680972-2019-11-20.xml*