# Percolation Theories for Multipartite Networked Systems under Random Failures

Authors: Qing Cai; Sameer Alam; Mahardhika Pratama; Zhen Wang
Journal: Complexity
 (2020)

---

## Abstract

Real-world complex systems inevitably suffer from perturbations. When some system components break down and trigger cascading failures on a system, the system will be out of control. In order to assess the tolerance of complex systems to perturbations, an effective way is to model a system as a network composed of nodes and edges and then carry out network robustness analysis. Percolation theories have proven as one of the most effective ways for assessing the robustness of complex systems. However, existing percolation theories are mainly for multilayer or interdependent networked systems, while little attention is paid to complex systems that are modeled as multipartite networks. This paper fills this void by establishing the percolation theories for multipartite networked systems under random failures. To achieve this goal, this paper first establishes two network models to describe how cascading failures propagate on multipartite networks subject to random node failures. Afterward, this paper adopts the largest connected component concept to quantify the networks’ robustness. Finally, this paper develops the corresponding percolation theories based on the developed network models. Simulations on computer-generated multipartite networks demonstrate that the proposed percolation theories coincide quite well with the simulations.


---

## Body

## 1. Introduction

It is universally acknowledged that complex systems are ubiquitous in our lives [1]. Complex systems like city transportation systems [2] and power supplier systems [3] are indispensable infrastructures to human life. In order to better understand complex systems so as to facilitate better service providing, an effective way is to model a complex system as a complex network composed of nodes and edges with the nodes denoting the system components and the edges representing the interactions between system components [4]. For example, a power grid system can be represented by a network in which a node denotes a power station and an edge denotes the transmission line between two stations. Complex network modeling and analysis have proven as a potent instrument for system control [5–7] and have received great popularity in the last two decades [8, 9].Note that complex systems in reality will inevitably suffer from external and/or internal unpredictable perturbations which can trigger cascading failures wreaking havoc on system structures and functionalities [5, 10]. A dramatic event in history was the Italian blackout that happened in 2003 [11]. It had been reported that the blackout was triggered by the breakdown of several power lines caused by a storm. It was until the seminal work done in [11] that the science underlying the event had been disclosed from the perspective of network robustness analysis. Network robustness analysis now has proven to be an effective approach to evaluating the robustness of complex systems so as to help prevent unseen system disasters [12–14]. Due to its significant economical values, many efforts have been made towards networked system robustness analysis. Existing studies can be roughly categorised into two classes, i.e., simulation-based studies [15–17] and theoretical studies [11, 18, 19]. Simulation-based studies investigate the robustness of networked systems by carrying out computer simulations. Their main drawback is that they cannot uncover the governing principles for system robustness. To overcome this drawback, theoretical studies came out and amongst which are the percolation theories [1, 20].Percolation on networks can not only measure the systems’ robustness but also provide the mathematical explanations for the systems’ robustness behaviours. Note that real-world systems are not independent but are organized in a layer-layer interdependent way, which are widely modeled as multilayer networks [18, 21, 22]. The component failures in one layer of a multilayer networked system can induce the failures in other layers and cascading failures could eventually occur. The work in [11] indicates that multilayer networked systems are vulnerable to perturbations and have sparked the research enthusiasm on the percolation theories for multilayer networked systems. Albeit the maturity of percolation theories for multilayer networked systems, little attention is paid to multipartite networked systems. Many complex systems like ecosystems [23, 24], certain control systems [1], and metabolic systems [25] can be modeled as multipartite networks. To explore the robustness of multipartite networked systems is also of great significance.The structure difference between multilayer and multipartite networks renders the applications of existing percolation theories to multipartite networked systems infeasible. With regard to this, for a given multipartite networked system, this paper first establishes two network cascading models to prescribe the way how cascading failures propagate on multipartite networks when initial node failures occur. Afterward, this paper develops the percolation theories for assessing the robustness of multipartite networked systems under random node failures based on the largest connected component concept.The remainder of this paper is structured as follows. Section2 provides related preliminaries including basic network notations, network robustness evaluation metrics, and percolation theory for single-layer networked systems. Section 3 presents the research problem and motivation. Section 4 delineates in detail the proposed percolation theories for analyzing the robustness of multipartite networked systems subject to random node failures. Section 5 validates the correctness of the proposed theories through simulations on random multipartite networks with Poisson degree distributions. Section 6 concludes the paper.


## 2. Preliminaries

### 2.1. Network Notations

Generally, a network is mathematically denoted byG=V,E, where V and E represent the sets of nodes and edges, respectively. The edges between nodes can be depicted by the adjacency matrix AN×N of G with N being the number of nodes in G. The matrix A is usually symmetric and binary. Let eij be the entry of A. If there is an edge between nodes i and j, then eij=1; otherwise, it is equal to 0.Regarding complex network analytics, one of the most concerned properties is the node degree. For a networkG, the degree ki of node i is defined as the number of edges attached to it. Generally, ki can be calculated as ki=∑j=0Neij. Another property is the degree distribution Pk of G which specifies the probability for a node to have degree k. With ki and Pk, we have the mean degree k of G, which can be calculated as k=1/N∑i=1Nki=∑k=0N−1kPk.


### 2.2. Multipartite and Multilayer Networked Systems

Definition 1.
Let us consider a complex system that can be modeled as a networkG whose node set V consists of L subsets, i.e., V=S1,S2,…,SL. If ∀a,b∈1,L, G satisfies the following conditions:(1)Sa∩Sb=∅,ifa≠b,eij∈0,1,ifi∈Sa∧j∈Sb∧b∈a−1,a+1,eij≡0,ifi∈Sa∧j∈Sa±k,∀k∈2,L−1,eij≡0,ifi,j∈Sa.Then, we say this system is a multipartite networked system and the network G is called a multipartite network.Remark 1.
The node setSa of a multipartite networked system can also be called a partite set. Equation (1) indicates that an edge of a multipartite network only happens between two nodes with one coming from partite set Sa and the other one from partite set Sa+1 or Sa−1.Definition 2.
Let us consider another system which can be modeled as a networkG, and G is composed of L subnetworks, i.e., G=G1,G2,…,GL. The node set V⊂G can also be divided into L subsets with Si being the node set for network Gi. If G satisfies the following conditions:(2)Sa∩Sb=∅,ifa≠b,eij∈0,1,ifi∈Sa∧j∈Sb∧b∈a,a−1,a+1,then we call this system a multilayer networked system and the network G is called a multilayer network [26, 27].Remark 2.
In the literature, a multilayer network can also be called an interdependent network or a network of networks [21, 28]. We can see from the above definitions that the only structural difference between a multilayer network and a multipartite network is that parallel edges (edges between nodes from the same node set) are not allowed in a multipartite network.


### 2.3. Networked System Robustness Evaluation

Network robustness analysis has proven as an effective tool for assessing the robustness of networked systems under disturbances [29, 30]. Regarding system robustness analysis, the foremost issue is how one defines or quantifies the robustness of a networked system. Hitherto, a handful of robustness metrics have been proposed by researchers, and most of them share the common idea as delineated in Figure 1.Figure 1
An illustration to the common idea shared by most existing metrics for quantifying the robustness of a networked system under node perturbations.In the left panel of Figure1 is a multilayer network G. Assume that G is under node perturbations and 1−p fraction of nodes is removed (marked in red in the figure). The node removals will trigger the cascading breakdown of other nodes and edges. Based on a prescribed cascading model which defines the way how cascading failures propagate on G, G finally reaches a stable stage (the final remaining part of G) in which no node/edge removal is possible. Then, one counts fp, the fraction of effective nodes, in the stable stage. One then gets the robustness curve drawn in the right panel of Figure 1 in which fp is shown with respect to p under different values.In the literature,fp is widely defined as the fraction of non-zero-degree nodes in the stable stage of G [15, 16, 24] after removing 1−p fraction of nodes. Based on this kind of definition for fp, the robustness of a network G then can be quantified by the node robustness index Rn devised in [16] or by the area index RA used in [15, 24]. The Rn index is calculated as Rn=∑p=01fp, while the RA index is measured as the area of the region covered by the robustness curve and the X-Y axis (see the dark region in the right panel of Figure 1). The larger the value of Rn or RA is, the higher robustness the focal network has.The above definition forfp is effective for network robustness analysis. However, scientists argue that this kind of definition may not reflect the real robustness of networks. In reality, the breakup of some components of a complex system will fragment the system into pieces and it is argued that only the largest piece will keep functioning. As per this assumption, scientists suggest the definition of fp as the fraction of nodes in the largest connected component (LCC, the subnetwork that contains the most nodes) in the stable stage G. The LCC-based definition for fp has been widely recognized [11, 21, 31], and this paper also adopts this kind of definition for network robustness analysis.Note that how to select the1−p fraction of nodes to be removed from a network depends on how one models the perturbations on the network [32–34]. Figure 1 only illustrates network robustness under node failures. In reality, failures can occur to the edges of a network. Meanwhile, many networks have been reported to possess community structures [35, 36]; therefore, failures can also occur to network communities. Related works can be found in [37, 38].


### 2.4. Percolation on Single-Layer Networked Systems

Percolation theories have gained large popularity for analyzing the robustness of networked systems [32, 39]. In the following we will illustrate the percolation theory for analyzing the robustness of single-layer networked systems.Given that a fraction1−p of nodes from a given single-layer network G is randomly removed, the node removal breaks G into small parts and there exists the largest one, i.e., the LCC. Percolation theory aims to mathematically figure out the fraction of nodes in the LCC, hereafter denoted by P∞, with respect to p and the degree distribution Pk of G [18, 40, 41], i.e., it aims to derive the relation P∞=Fp,Pk with F⋅ being a map or a function. Before presenting the mathematical derivations, we first present in the following some related definitions.Definition 3 (generating function).
A generating function for a degree distributionPk is defined as(3)G0x=∑k=0∞xkPk,where k is the degree of a node and x is an arbitrary placeholder.Definition 4.
(excess degree distribution). Following a randomly chosen edge we reach a nodes. Define the excess degree distribution PEk as the probability for node s to have k extra neighbours.Remark 3.
The excess degree distribution practically denotes the probability for a randomly chosen node to have degreek+1. In the literature [1, 42], PEk is widely calculated as(4)PEk=k+1Pk+1k.Remark 4.
Analogous to equation (3), the generating function for PEk is formulated as(5)G1x=∑k=0∞xkPEk=G0′xG0′1,with G0′x being the first-order derivative of G0x.
With the above definitions, the percolation theory for calculatingP∞ for a single-layer network G can be mathematically written as(6)P∞=p∑k=0∞Pk1−uk=p1−G0u,with u being the probability for node s (reached by following a randomly chosen edge) not to be connected to the LCC via its neighbouring node d.
The probability variableu is calculated by the following transcendental equation:(7)u=∑k=0∞1−p+pukPEk=1−p+pG1u.
There exists a critical value ofp, denoted by pc. Once the fraction of node removal surpasses 1−pc, then the focal network G will break down, i.e., P∞=0. The critical value appears when the right and left panels of equation (7) meet with each other tangentially at u=1. By calculating the derivative of equation (7), we have(8)dudu=dpcG1uduu=1,which further leads to(9)pc=kk2−k,in which k2=∑k2Pk is the second moment of Pk. Generally, the smaller the value of pc is, the more robust the focal network is.


## 2.1. Network Notations

Generally, a network is mathematically denoted byG=V,E, where V and E represent the sets of nodes and edges, respectively. The edges between nodes can be depicted by the adjacency matrix AN×N of G with N being the number of nodes in G. The matrix A is usually symmetric and binary. Let eij be the entry of A. If there is an edge between nodes i and j, then eij=1; otherwise, it is equal to 0.Regarding complex network analytics, one of the most concerned properties is the node degree. For a networkG, the degree ki of node i is defined as the number of edges attached to it. Generally, ki can be calculated as ki=∑j=0Neij. Another property is the degree distribution Pk of G which specifies the probability for a node to have degree k. With ki and Pk, we have the mean degree k of G, which can be calculated as k=1/N∑i=1Nki=∑k=0N−1kPk.


## 2.2. Multipartite and Multilayer Networked Systems

Definition 1.
Let us consider a complex system that can be modeled as a networkG whose node set V consists of L subsets, i.e., V=S1,S2,…,SL. If ∀a,b∈1,L, G satisfies the following conditions:(1)Sa∩Sb=∅,ifa≠b,eij∈0,1,ifi∈Sa∧j∈Sb∧b∈a−1,a+1,eij≡0,ifi∈Sa∧j∈Sa±k,∀k∈2,L−1,eij≡0,ifi,j∈Sa.Then, we say this system is a multipartite networked system and the network G is called a multipartite network.Remark 1.
The node setSa of a multipartite networked system can also be called a partite set. Equation (1) indicates that an edge of a multipartite network only happens between two nodes with one coming from partite set Sa and the other one from partite set Sa+1 or Sa−1.Definition 2.
Let us consider another system which can be modeled as a networkG, and G is composed of L subnetworks, i.e., G=G1,G2,…,GL. The node set V⊂G can also be divided into L subsets with Si being the node set for network Gi. If G satisfies the following conditions:(2)Sa∩Sb=∅,ifa≠b,eij∈0,1,ifi∈Sa∧j∈Sb∧b∈a,a−1,a+1,then we call this system a multilayer networked system and the network G is called a multilayer network [26, 27].Remark 2.
In the literature, a multilayer network can also be called an interdependent network or a network of networks [21, 28]. We can see from the above definitions that the only structural difference between a multilayer network and a multipartite network is that parallel edges (edges between nodes from the same node set) are not allowed in a multipartite network.


## 2.3. Networked System Robustness Evaluation

Network robustness analysis has proven as an effective tool for assessing the robustness of networked systems under disturbances [29, 30]. Regarding system robustness analysis, the foremost issue is how one defines or quantifies the robustness of a networked system. Hitherto, a handful of robustness metrics have been proposed by researchers, and most of them share the common idea as delineated in Figure 1.Figure 1
An illustration to the common idea shared by most existing metrics for quantifying the robustness of a networked system under node perturbations.In the left panel of Figure1 is a multilayer network G. Assume that G is under node perturbations and 1−p fraction of nodes is removed (marked in red in the figure). The node removals will trigger the cascading breakdown of other nodes and edges. Based on a prescribed cascading model which defines the way how cascading failures propagate on G, G finally reaches a stable stage (the final remaining part of G) in which no node/edge removal is possible. Then, one counts fp, the fraction of effective nodes, in the stable stage. One then gets the robustness curve drawn in the right panel of Figure 1 in which fp is shown with respect to p under different values.In the literature,fp is widely defined as the fraction of non-zero-degree nodes in the stable stage of G [15, 16, 24] after removing 1−p fraction of nodes. Based on this kind of definition for fp, the robustness of a network G then can be quantified by the node robustness index Rn devised in [16] or by the area index RA used in [15, 24]. The Rn index is calculated as Rn=∑p=01fp, while the RA index is measured as the area of the region covered by the robustness curve and the X-Y axis (see the dark region in the right panel of Figure 1). The larger the value of Rn or RA is, the higher robustness the focal network has.The above definition forfp is effective for network robustness analysis. However, scientists argue that this kind of definition may not reflect the real robustness of networks. In reality, the breakup of some components of a complex system will fragment the system into pieces and it is argued that only the largest piece will keep functioning. As per this assumption, scientists suggest the definition of fp as the fraction of nodes in the largest connected component (LCC, the subnetwork that contains the most nodes) in the stable stage G. The LCC-based definition for fp has been widely recognized [11, 21, 31], and this paper also adopts this kind of definition for network robustness analysis.Note that how to select the1−p fraction of nodes to be removed from a network depends on how one models the perturbations on the network [32–34]. Figure 1 only illustrates network robustness under node failures. In reality, failures can occur to the edges of a network. Meanwhile, many networks have been reported to possess community structures [35, 36]; therefore, failures can also occur to network communities. Related works can be found in [37, 38].


## 2.4. Percolation on Single-Layer Networked Systems

Percolation theories have gained large popularity for analyzing the robustness of networked systems [32, 39]. In the following we will illustrate the percolation theory for analyzing the robustness of single-layer networked systems.Given that a fraction1−p of nodes from a given single-layer network G is randomly removed, the node removal breaks G into small parts and there exists the largest one, i.e., the LCC. Percolation theory aims to mathematically figure out the fraction of nodes in the LCC, hereafter denoted by P∞, with respect to p and the degree distribution Pk of G [18, 40, 41], i.e., it aims to derive the relation P∞=Fp,Pk with F⋅ being a map or a function. Before presenting the mathematical derivations, we first present in the following some related definitions.Definition 3 (generating function).
A generating function for a degree distributionPk is defined as(3)G0x=∑k=0∞xkPk,where k is the degree of a node and x is an arbitrary placeholder.Definition 4.
(excess degree distribution). Following a randomly chosen edge we reach a nodes. Define the excess degree distribution PEk as the probability for node s to have k extra neighbours.Remark 3.
The excess degree distribution practically denotes the probability for a randomly chosen node to have degreek+1. In the literature [1, 42], PEk is widely calculated as(4)PEk=k+1Pk+1k.Remark 4.
Analogous to equation (3), the generating function for PEk is formulated as(5)G1x=∑k=0∞xkPEk=G0′xG0′1,with G0′x being the first-order derivative of G0x.
With the above definitions, the percolation theory for calculatingP∞ for a single-layer network G can be mathematically written as(6)P∞=p∑k=0∞Pk1−uk=p1−G0u,with u being the probability for node s (reached by following a randomly chosen edge) not to be connected to the LCC via its neighbouring node d.
The probability variableu is calculated by the following transcendental equation:(7)u=∑k=0∞1−p+pukPEk=1−p+pG1u.
There exists a critical value ofp, denoted by pc. Once the fraction of node removal surpasses 1−pc, then the focal network G will break down, i.e., P∞=0. The critical value appears when the right and left panels of equation (7) meet with each other tangentially at u=1. By calculating the derivative of equation (7), we have(8)dudu=dpcG1uduu=1,which further leads to(9)pc=kk2−k,in which k2=∑k2Pk is the second moment of Pk. Generally, the smaller the value of pc is, the more robust the focal network is.


## 3. Problem Definition and Research Motivation

### 3.1. Problem Definition

This paper is dedicated to mathematically investigating the robustness of multipartite networks. Below we present the mathematical definition for our studied problem.Definition 5.
(research problem). Consider a system that is modeled as anL-partite network G. Denote Gij, Gij⊂G, as the bipartite network composed of node sets Si and Sj with j∈i−1,i+1. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for all i∈1,L and pi∈0,1. For a given network cascading model which specifies how cascading failures propagate on G, G then reaches a stable stage. Consider the LCC in the stable stage of G. Then, the research problem is to derive the relation(10)Pi∞=Fpi,P12k,…,Pijk,…,PL,L−1k,with Pi∞ being the fraction of nodes remaining in Si⊂G which also belongs to the LCC and Pijk being the degree distribution for the nodes in Si⊂Gij.


### 3.2. Research Motivation

From the definitions given in Section2.1, one may argue that a multipartite network can be regarded as a simplified multilayer network and in turn a multilayer network can be regarded as a relaxation of a multipartite network. Therefore, one may think that models and theories developed for multilayer networks will work for multipartite networks. In what follows, we elaborate in detail our research motivations for proposing the percolation theories for multipartite networks.(M1) Limitation of Percolation Theory for Multilayer Networks with One-to-One CorrelationsThe percolation theory introduced in Section2.4 is for single-layer networks and therefore does not work for multilayer networks. In view of this, the authors in [11] first investigated the robustness of multilayer networks with one-to-one (O2O) correlations, i.e., each node in one subnetwork depends on one and only one node in its coupled subnetwork. Similar network models can be found in [18, 21].Figure2 exhibits the dynamic cascading model established in [11] for analyzing the robustness of multilayer networks with O2O correlations. This model assumes that for each subnetwork contained in a multilayer network, only the nodes that belong to the LCC will survive perturbations and cascading failures will not stop until a mutual LCC is reached.Figure 2
Dynamic network model for analyzing the robustness of multilayer networked systems with one-to-one correlations. Initially, node 5 from network A is removed. Due to the O2O correlations, node 5 in network B is also eliminated in Stage 1 and network A breaks into three clusters, denoted bya11, a12, and a13. In Stage 2, nodes 4 and 6 both in networks A and B together with the links attached to them are removed, and network B breaks into four clusters, namely, b21, b22, b23, and b24. In Stage 3, node 3 in network A is removed and network A breaks into four clusters. Because in Stage 3 no further link elimination and network breaking occur, the cluster consisting of a34 and b24, also the LCC, survives.Based on the model illustrated in Figure2, the authors further devised the corresponding percolation theory. Obviously, the model shown in Figure 2 together with its corresponding theory is not applicable to multipartite networks. The reason is obvious as a multipartite network does not obey the O2O correlation hypothesis.(M2) Limitation of Percolation Theory for Multilayer Networks with One-to-Many CorrelationsReal-world multilayer networks are often one-to-many (O2M) correlated, i.e., each node in one subnetwork depends on more than one node in its coupled subnetwork. With regard to this, studies on the robustness of multilayer networks with O2M correlations came out [31, 43, 44].Figure3 shows the dynamic cascading model proposed in [18] for analyzing the robustness of multilayer networks with O2M correlations. Given a two-layer network consisting of subnetworks A and B, let P˜Ak (and P˜Bk) be the degree distribution of the nodes in A (and B) that have correlations with nodes in B (and A). Assume that a fraction 1−pA and a fraction 1−pB of nodes are randomly removed from A and B, respectively. With the model shown in Figure 3 the authors then have devised the corresponding percolation theory which is mathematically written as(11)PA∞=uA1−GA01−uA1−fA,PB∞=uB1−GB01−uB1−fB,where G˜A0 and G˜B0 are, respectively, the generating functions of P˜Ak and P˜Bk. The corresponding variables fA, fB, uA, and uB are calculated as(12)fA=GA11−uA1−fA,fB=GB11−uB1−fB,uA=pA1−G˜A01−PB∞,uB=pB1−G˜B01−PA∞.Figure 3
Dynamic network model for analyzing the robustness of multilayer networked systems with one-to-many correlations. Arrows represent the support links connecting a support node in one network to the dependent node in the other network. Initially, the attacks are on node 1 in A and node 6 in B. For network A in Stage 1, node 7 fails because it has no support links, and nodes 2 and 6 are eliminated because they do not belong to the LCC of A. For network B in Stage 1, nodes 1, 2, and 7 fail because of no support, and node 3 is removed since it is not in the LCC of B. The above processes continue until a stable state is reached.Note that a multipartite network can be regarded as a simplified multilayer network with O2M correlations. However, the model shown in Figure3 still does not work for multipartite networks. The reasons are twofold. On the one hand, the model shown in Figure 3 considers the LCC of the network in each layer, while the nodes in each “layer” of a multipartite network are disconnected from each other, and thus the LCC does not exist. On the other hand, the percolation theory based on the model shown in Figure 3 involves the degree distributions PAk and PBk. Bear in mind that PAk denotes the degree distribution of the nodes in network A that have connections with each other. Thus, we have PAk=PBk=⋯≡0 for a multipartite network, and the substitution of this condition into equation (11) will lead to the following result:(13)PA∞=pA1−GA01−PB∞,PB∞=pB1−GB01−PA∞.For one thing, the above equation only works for bipartite networks. For another thing, the extension of the above equation definitely does not fit for multipartite networks because equation (11) is based on the dynamic model shown in Figure 3 which is not applicable to multipartite networks. One more thing is that the derivations of equation (11) are very complicated. Therefore, new models and theories for analyzing the robustness of multipartite networks are desirable, and this is the very motivation of this work.


## 3.1. Problem Definition

This paper is dedicated to mathematically investigating the robustness of multipartite networks. Below we present the mathematical definition for our studied problem.Definition 5.
(research problem). Consider a system that is modeled as anL-partite network G. Denote Gij, Gij⊂G, as the bipartite network composed of node sets Si and Sj with j∈i−1,i+1. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for all i∈1,L and pi∈0,1. For a given network cascading model which specifies how cascading failures propagate on G, G then reaches a stable stage. Consider the LCC in the stable stage of G. Then, the research problem is to derive the relation(10)Pi∞=Fpi,P12k,…,Pijk,…,PL,L−1k,with Pi∞ being the fraction of nodes remaining in Si⊂G which also belongs to the LCC and Pijk being the degree distribution for the nodes in Si⊂Gij.


## 3.2. Research Motivation

From the definitions given in Section2.1, one may argue that a multipartite network can be regarded as a simplified multilayer network and in turn a multilayer network can be regarded as a relaxation of a multipartite network. Therefore, one may think that models and theories developed for multilayer networks will work for multipartite networks. In what follows, we elaborate in detail our research motivations for proposing the percolation theories for multipartite networks.(M1) Limitation of Percolation Theory for Multilayer Networks with One-to-One CorrelationsThe percolation theory introduced in Section2.4 is for single-layer networks and therefore does not work for multilayer networks. In view of this, the authors in [11] first investigated the robustness of multilayer networks with one-to-one (O2O) correlations, i.e., each node in one subnetwork depends on one and only one node in its coupled subnetwork. Similar network models can be found in [18, 21].Figure2 exhibits the dynamic cascading model established in [11] for analyzing the robustness of multilayer networks with O2O correlations. This model assumes that for each subnetwork contained in a multilayer network, only the nodes that belong to the LCC will survive perturbations and cascading failures will not stop until a mutual LCC is reached.Figure 2
Dynamic network model for analyzing the robustness of multilayer networked systems with one-to-one correlations. Initially, node 5 from network A is removed. Due to the O2O correlations, node 5 in network B is also eliminated in Stage 1 and network A breaks into three clusters, denoted bya11, a12, and a13. In Stage 2, nodes 4 and 6 both in networks A and B together with the links attached to them are removed, and network B breaks into four clusters, namely, b21, b22, b23, and b24. In Stage 3, node 3 in network A is removed and network A breaks into four clusters. Because in Stage 3 no further link elimination and network breaking occur, the cluster consisting of a34 and b24, also the LCC, survives.Based on the model illustrated in Figure2, the authors further devised the corresponding percolation theory. Obviously, the model shown in Figure 2 together with its corresponding theory is not applicable to multipartite networks. The reason is obvious as a multipartite network does not obey the O2O correlation hypothesis.(M2) Limitation of Percolation Theory for Multilayer Networks with One-to-Many CorrelationsReal-world multilayer networks are often one-to-many (O2M) correlated, i.e., each node in one subnetwork depends on more than one node in its coupled subnetwork. With regard to this, studies on the robustness of multilayer networks with O2M correlations came out [31, 43, 44].Figure3 shows the dynamic cascading model proposed in [18] for analyzing the robustness of multilayer networks with O2M correlations. Given a two-layer network consisting of subnetworks A and B, let P˜Ak (and P˜Bk) be the degree distribution of the nodes in A (and B) that have correlations with nodes in B (and A). Assume that a fraction 1−pA and a fraction 1−pB of nodes are randomly removed from A and B, respectively. With the model shown in Figure 3 the authors then have devised the corresponding percolation theory which is mathematically written as(11)PA∞=uA1−GA01−uA1−fA,PB∞=uB1−GB01−uB1−fB,where G˜A0 and G˜B0 are, respectively, the generating functions of P˜Ak and P˜Bk. The corresponding variables fA, fB, uA, and uB are calculated as(12)fA=GA11−uA1−fA,fB=GB11−uB1−fB,uA=pA1−G˜A01−PB∞,uB=pB1−G˜B01−PA∞.Figure 3
Dynamic network model for analyzing the robustness of multilayer networked systems with one-to-many correlations. Arrows represent the support links connecting a support node in one network to the dependent node in the other network. Initially, the attacks are on node 1 in A and node 6 in B. For network A in Stage 1, node 7 fails because it has no support links, and nodes 2 and 6 are eliminated because they do not belong to the LCC of A. For network B in Stage 1, nodes 1, 2, and 7 fail because of no support, and node 3 is removed since it is not in the LCC of B. The above processes continue until a stable state is reached.Note that a multipartite network can be regarded as a simplified multilayer network with O2M correlations. However, the model shown in Figure3 still does not work for multipartite networks. The reasons are twofold. On the one hand, the model shown in Figure 3 considers the LCC of the network in each layer, while the nodes in each “layer” of a multipartite network are disconnected from each other, and thus the LCC does not exist. On the other hand, the percolation theory based on the model shown in Figure 3 involves the degree distributions PAk and PBk. Bear in mind that PAk denotes the degree distribution of the nodes in network A that have connections with each other. Thus, we have PAk=PBk=⋯≡0 for a multipartite network, and the substitution of this condition into equation (11) will lead to the following result:(13)PA∞=pA1−GA01−PB∞,PB∞=pB1−GB01−PA∞.For one thing, the above equation only works for bipartite networks. For another thing, the extension of the above equation definitely does not fit for multipartite networks because equation (11) is based on the dynamic model shown in Figure 3 which is not applicable to multipartite networks. One more thing is that the derivations of equation (11) are very complicated. Therefore, new models and theories for analyzing the robustness of multipartite networks are desirable, and this is the very motivation of this work.


## 4. Proposed Models and Theories

### 4.1. Global Model for Robustness Analysis

Although the models exhibited in Figures2 and 3 are not feasible for multipartite networked systems, their ideas could provide us inspirations. Equipped with the concept of LCC, we first establish a simple cascading model, which we call it the global model, for multipartite networks.Definition 6.
(global model). Consider anL-partite network G with Si being its i-th node set. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for ∀i∈1,L and pi∈0,1. The edges attached to the removed nodes are also removed. The removal of nodes and edges fragments G into small parts, and the largest one is regarded as the LCC of G and only the LCC will survive in the final stable stage.Example 1.
Figure4 gives a graphical example of the global model for defining the way how failures propagate on multipartite networks. We can observe from Figure 4 that the global model practically takes a multipartite network as a whole. When a multipartite network is under attack, the global model directly calculates the LCC in the network.Figure 4
An example of the global model for describing the cascading failures on multipartite networked systems subject to node failures. Initially, node 2 from partite set B of a tripartite network is removed. In Stage 1, the removal of node 2 breaks the focal network into two clusters, and all the nodes that are not in the LCC are removed. In the final stage, only the nodes in the LCC are remaining.


### 4.2. Local Model for Robustness Analysis

The global model is simple and straightforward. However, it may not reflect the dynamics of all types of multipartite networks. Inspired by the models proposed in [11, 18], we further develop another cascading model which we call it the local model.Definition 7.
(local model). Consider anL-partite network G with Si being its i-th node set. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for ∀i∈1,L and pi∈0,1. The edges attached to the removed nodes are also removed. The removal of nodes and edges fragments G12⊂G into small parts, and the nodes outside the LCC of G12, together with their edges, are removed. The removal of nodes and edges further fragments G23⊂G into small parts, and nodes outside the LCC of G23 are removed. The node removal and network fragmentation processes repeat recursively on Gij⊂G for all i∈1,L−1 until G reaches a stable stage in which no node/edge removal and network fragmentations are possible. Then, the remaining subnetwork in the stable stage is the LCC of G.Example 2.
Figure5 presents a graphical example of the proposed local model for depicting the dynamic process on a multipartite network under node failures. It can be noticed from Figure 5 that the local model considers the LCC in each bipartite network contained in a multipartite network. In the final stable stage, the local model focuses on the LCC that contains nodes from every partite set of the multipartite network in question.Figure 5
An example of the local model for describing the cascading failures on multipartite networked systems subject to node failures. Initially, node 2 from partite set B is removed. In Stage 1, the local model considers the LCC of the bipartite networkGAB containing the nodes in A and B. In Stage 2, the nodes that are not in the LCC of GAB are removed. In Stage 3, the local model considers the LCC of the bipartite network GBC containing the nodes in B and C. In Stage 4, the nodes that are not in the LCC of GBC are removed. The above process continues until no further node removal is possible. The remaining subnetwork in the stable stage is considered as the LCC of the focal network.


### 4.3. Variables and Notations

Before starting depicting our proposed theories for analyzing the robustness of multipartite networks, we first list out related variables and notations that will be heavily used in our later derivations.Given anL-partite network G with Si being its i-th partite set and ni=Si being the number of nodes in Si, let Pik be the degree distribution of the nodes in Si. Denote Gij⊂G as the bipartite network consisting of partite sets Si and Sj with j=i−1,i+1. Let Pijk be the degree distribution of the nodes in Si⊂Gij that have connections with nodes in Si⊂Gij.Based on the definition of excess degree distribution, we, respectively, define the excess degree distributions ofPik and Pijk as PiEk and PijEk. Then, based on the definition of generating function, we define Gi0x=∑k=0∞xkPik and Gij0x=∑k=0∞xkPijk, respectively, as the generating functions for Pik and Pijk. Analogously, we define Gi1x=∑k=0∞xkPiEk and Gij1x=∑k=0∞xkPijEk, respectively, as the generating functions for PiEk and PijEk.


### 4.4. Percolation Theory Based on the Global Model

With all the above defined variables, for anL-partite networked system, we propose the following percolation theory for calculating Pi∞ with respect to the global model presented in Definition 6.Definition 8.
(probability vectoru). Consider the situation that 1−pi fraction of nodes is randomly removed from Si of an L-partite network G for ∀i∈1,L with pi∈0,1. For j∈i−1,i+1, define a probability vector u=u12,u21,…,uij,…,uL,L−1, with uij being the probability for a node in Si not to be connected to the LCC of G via a node in Sj.Theorem 1.
(percolation theory based on the global model). Consider anL-partite network G with L≥3; we randomly remove 1−pi fraction of nodes from Si for ∀i∈1,L with pi∈0,1. Based on the global model given in Definition 4, G reaches a stable stage. Define the probability vector u. In the limit of ni⟶∞, the fraction Pi∞ of nodes in Si that also belongs to the LCC in the stable stage of G is calculated as(14)P1∞=p11−G120u12,Pi∞=pi1−∏j=i−1,i+1Gij0uij,∀i∈2,L−1,PL∞=pL1−GL,L−10uL,L−1,with the variable uij∈u being calculated as(15)u21=1−p1+p1G121u12,uij=1−pj+pjGji1ujiGj,j+δ1uj,j+δ,uL−1,L=1−pL+pLGL,L−11uL,L−1,where δ=−1, if j=i−1, and δ=1, if j=i+1.Proof.
We start by consideringP1∞. As the probability for a node a∈S1 not to be connected to the LCC via a node b∈S2 is u12, the probability ϕ12 for nodes in S1 not to be connected to the LCC via nodes in S2 is calculated as(16)ϕ12=∑k=0n2P12ku12k.
In the limit ofni⟶∞, we have(17)limn2⟶∞ϕ12=∑k=0∞P12ku12k=G120u12.
Note that1−pi fraction of nodes is removed from Si for ∀i∈1,L; thus, pi fraction of nodes is remaining in Si. Therefore, in the LCC of G, the remaining fraction of nodes in S1 is calculated as(18)P1∞=p11−ϕ12=p11−G120u12.
Analogously, we can prove the correctness of the expression ofPL∞ as given in Theorem 1. Now, let us consider Pi∞.
Note that a nodea∈Si can simultaneously have neighbours in Si−1 and Si+1. If nodes in Si do not belong to the LCC, then the nodes in Si should not be connected to the LCC via their neighbours. Based on the above analysis, we know that the probability ϕi,i−1 for nodes in Si not to be connected to the LCC via nodes in Si−1 is(19)ϕi,i−1=∑k=0ni−1Pi,i−1kui,i−1k.
Analogously, the probabilityϕi,i+1 for nodes in Si not to be connected to the LCC via nodes in Si+1 is(20)ϕi,i+1=∑k=0ni+1Pi,i+1kui,i+1k.
Then, the probabilityϕi for nodes in Si not to be connected to the LCC via their neighbours is ϕi=ϕi,i−1⋅ϕi,i+1. Therefore, in the limit of ni⟶∞, we further have(21)limni⟶∞ϕi=Gi,i−10ui,i−1Gi,i+10ui,i+1,based on which we can figure out Pi∞ as(22)Pi∞=pi1−ϕi=pi1−Gi,i−10ui,i−1Gi,i+10ui,i+1.
To this end, the first part of Theorem1, i.e., the part regarding Pi∞, is proved. Next, we give the proof for the second part regarding the probability vector u.
We start by analyzingu21, which denotes the probability for the event that a node b∈S2 is not connected to the LCC of G via a node a∈S1 to happen. Note that if node a is removed, which happens with a probability 1−p1, then the above event obviously happens. Now, consider the situation that node a is not removed. Then, the aforementioned event happens if a is not connected to the LCC via its neighbours. As a consequence, in the limit of ni⟶∞, we have(23)u21=1−p1+p1∑k=0n2P12Eku12k=1−p1+p1⋅G121u12.
Analogously, we can prove the correctness of the expression ofuL−1,L. Next, we consider uij with j=i+1.
Note that nodes inSi have connections with nodes in Sj. The event that a node a∈Si is not connected to the LCC via a node b∈Sj, which happens with the probability uij, can happen under two situations: (S1) node b has been removed; (S2) node b is not removed and b itself is not connected to the LCC via its own neighbours. Situation S1 happens with the probability ψS1=1−pj. Thus, the key step for working out uij then lies in the calculation of the probability ψS2 for situation S2 to happen.
Because a nodeb∈Sj can simultaneously have neighbours in Si and Sj+1, if b is not connected to the LCC via its neighbours, then b should neither be connected to the LCC via nodes in Si nor via nodes in Sj+1. Assume that node b has k neighbours in Si; then, the probability φji for node b not to be connected to the LCC via nodes in Si is(24)φji=ujik.
Analogously, when nodeb has k neighbours in Sj+1, the probability φj,j+1 for node b not to be connected to the LCC via nodes in Sj+1 is(25)φj,j+1=uj,j+1k.
Recall the definition of excess degree distribution; the probabilities for nodeb to, respectively, have k neighbours in Si and k neighbours in Sj+1 are PjiEk and Pj,j+1Ek. As a consequence, the probability ψS2 can be calculated as(26)ψS2=pj∑k=0niPjiEkφji∑k=0nj+1Pj,j+1Ekφj,j+1.
Note that situations S1 and S2 are two independent events; therefore, in the limit ofni⟶∞, the probability uij is calculated as(27)uij=ψS1+ψS2=1−pj+pjGji1ujiGj,j+11uj,j+1.
The proof ofuij for j=i−1 is omitted as it is analogous to that of uij for j=i+1 as presented above. To this end, Theorem 1 is proved.Remark 5.
Note that when analyzingψS2, it is easy to derive the wrong expression of ψS2 in the following way:(28)ψS2=pj∑k=0∞PjEk∑m=0kkmujimuj,j+1k−m=pjGj1uji+uj,j+1.
The idea of the above derivations is thatm out of k neighbours of a node b∈Sj are not connected to the LCC via nodes in Si, and the remaining k−m neighbours of b are not connected to the LCC via nodes in Sj+1. However, the event that node b has k neighbours in Si and the event that node b has k neighbours in Sj+1 are independent. Therefore, variable m does not need to run over k for k∈0,∞.Remark 6.
From Theorem1, one can easily derive the percolation theory for L-partite networked systems with L=2, i.e., bipartite networked systems. Specifically, one can have(29)P1∞=p11−G120u12,P2∞=p21−G210u21,with u12 and u21, respectively, being calculated as(30)u12=1−p2+p2G211u21,u21=1−p1+p1G121u12.


### 4.5. Percolation Theory Based on the Local Model

When calculating the LCC, the global model takes a multipartite network as a whole while the local model by contrast analyzes its subnetworks. The local model requires that the final LCC should encompass nodes from every partite set. Therefore, the above proposed percolation theory does not work for multipartite networked systems with respect to the local model. In what follows we elucidate our proposed percolation theory based on the local model.Theorem 2.
(percolation theory based on the local model). Consider anL-partite network G with L≥3; we randomly remove 1−pi fraction of nodes from Si for ∀i∈1,L with pi∈0,1. Based on the local model given in Definition 5, G reaches a stable stage. Define the probability vector u. In the limit of ni⟶∞, the fraction Pi∞ of nodes in Si which also belongs to the LCC in the stable stage of G is calculated as(31)P1∞=p11−G120u12,Pi∞=pi∏j=i−1,i+11−Gij0uij,i∈2,L−1,PL∞=pL1−GL,L−10uL,L−1,with the variable uij being calculated as(32)u21=1−p1+p1G121u12,uij=1−pj1−Gji1uji1−Gj,j+δ1uj,j+δ,uL−1,L=1−pL+pLGL,L−11uL,L−1,where δ=−1, if j=i−1, and δ=1, if j=i+1.Proof.
We only present the proof forPi∞, since the proofs for P1∞ and PL∞ are exactly the same as that presented in Theorem 1. As mentioned earlier, a node a∈Si can simultaneously have neighbours in Si−1 and Si+1. Based on the local model given in Definition 5, we see that as long as there exists one neighbour of node a that connects a to the LCC, then node a definitely belongs to the LCC. According to the proof of Theorem 1, we know that in the limit of ni⟶∞, the probability ϕi,i−1 for nodes in Si not to be connected to the LCC via nodes in Si−1 is(33)ϕi,i−1=Gi,i−10ui,i−1.
Analogously, we haveϕi,i+1=Gi,i+10ui,i+1. Therefore, the probability for node a to be connected to the LCC via at least one neighbour in Si−1 is 1−ϕi,i−1. Analogously, the probability for node a to be connected to the LCC via at least one neighbour in Si+1 is 1−ϕi,i+1. Consequently, the probability ϕi¯ for nodes in Si to be connected to the LCC via their neighbours is calculated as(34)ϕi¯=1−ϕi=1−ϕi,i−11−ϕi,i+1.
Therefore, in the limit ofni⟶∞, Pi∞ is calculated as(35)Pi∞=piϕi¯=pi1−ϕi,i−11−ϕi,i+1=pi∏j=i−1,i+11−Gij0uij.
To this end, the correctness ofPi∞ as given in Theorem 2 is proved. Next, we give the proof for the probability variable uij. The proofs for variables u21 and uL−1,L are omitted as they are the same as that given in the proof for Theorem 1. We first analyze uij with j=i+1.
Recall that the variableuij denotes the probability that a node a∈Si is not connected to the LCC via a node b∈Sj. Analogous to what are analyzed in the proof for Theorem 1, the event that a∈Si is not connected to the LCC via b∈Sj also happens under two situations: (S1) node b is removed, which happens with the probability ψS1=1−pj; (S2) b remains and b is not connected to the LCC via its neighbours. Note that the probability ψS2 for situation S2 to happen cannot be calculated in the way demonstrated in the proof of Theorem 1. The reason is that the local model requires that the LCC contains nodes from Si for ∀i∈1,L, while the global model does not require this condition.
Because nodeb∈Sj has neighbours in Si and Sj+1, the probabilities φji and φj,j+1 are, respectively, calculated as φji=ujik and φj,j+1=uj,j+1k. Therefore, the probability φj for b∈Sj neither to be connected to the LCC via neighbours in Si nor via nodes in Sj+1 is(36)φi=∑k=0niPjiEkφji+∑k=0nj+1Pj,j+1Ekφj,j+1−∑k=0niPjiEkφji∑k=0nj+1Pj,j+1Ekφj,j+1.
In the limit ofni⟶∞, φi can be further calculated as(37)limni⟶∞φi=Gji1uji+Gj,j+11uj,j+1−Gji1ujiGj,j+11uj,j+1.
AsψS2=pjφi, in the limit of ni⟶∞, the probability uij is calculated as(38)uij=ψS1+ψS2=1−pj+pjφi=1−pj1−Gji1uji1−Gj,j+11uj,j+1.
Based on the same token shown above, we can work outuij for j=i−1 as(39)uij=1−pj1−Gji1uji1−Gj,j−11uj,j−1,and therefore Theorem 2 is proved.


## 4.1. Global Model for Robustness Analysis

Although the models exhibited in Figures2 and 3 are not feasible for multipartite networked systems, their ideas could provide us inspirations. Equipped with the concept of LCC, we first establish a simple cascading model, which we call it the global model, for multipartite networks.Definition 6.
(global model). Consider anL-partite network G with Si being its i-th node set. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for ∀i∈1,L and pi∈0,1. The edges attached to the removed nodes are also removed. The removal of nodes and edges fragments G into small parts, and the largest one is regarded as the LCC of G and only the LCC will survive in the final stable stage.Example 1.
Figure4 gives a graphical example of the global model for defining the way how failures propagate on multipartite networks. We can observe from Figure 4 that the global model practically takes a multipartite network as a whole. When a multipartite network is under attack, the global model directly calculates the LCC in the network.Figure 4
An example of the global model for describing the cascading failures on multipartite networked systems subject to node failures. Initially, node 2 from partite set B of a tripartite network is removed. In Stage 1, the removal of node 2 breaks the focal network into two clusters, and all the nodes that are not in the LCC are removed. In the final stage, only the nodes in the LCC are remaining.


## 4.2. Local Model for Robustness Analysis

The global model is simple and straightforward. However, it may not reflect the dynamics of all types of multipartite networks. Inspired by the models proposed in [11, 18], we further develop another cascading model which we call it the local model.Definition 7.
(local model). Consider anL-partite network G with Si being its i-th node set. Assume that G is under random attack and 1−pi fraction of nodes is randomly removed from Si⊂G for ∀i∈1,L and pi∈0,1. The edges attached to the removed nodes are also removed. The removal of nodes and edges fragments G12⊂G into small parts, and the nodes outside the LCC of G12, together with their edges, are removed. The removal of nodes and edges further fragments G23⊂G into small parts, and nodes outside the LCC of G23 are removed. The node removal and network fragmentation processes repeat recursively on Gij⊂G for all i∈1,L−1 until G reaches a stable stage in which no node/edge removal and network fragmentations are possible. Then, the remaining subnetwork in the stable stage is the LCC of G.Example 2.
Figure5 presents a graphical example of the proposed local model for depicting the dynamic process on a multipartite network under node failures. It can be noticed from Figure 5 that the local model considers the LCC in each bipartite network contained in a multipartite network. In the final stable stage, the local model focuses on the LCC that contains nodes from every partite set of the multipartite network in question.Figure 5
An example of the local model for describing the cascading failures on multipartite networked systems subject to node failures. Initially, node 2 from partite set B is removed. In Stage 1, the local model considers the LCC of the bipartite networkGAB containing the nodes in A and B. In Stage 2, the nodes that are not in the LCC of GAB are removed. In Stage 3, the local model considers the LCC of the bipartite network GBC containing the nodes in B and C. In Stage 4, the nodes that are not in the LCC of GBC are removed. The above process continues until no further node removal is possible. The remaining subnetwork in the stable stage is considered as the LCC of the focal network.


## 4.3. Variables and Notations

Before starting depicting our proposed theories for analyzing the robustness of multipartite networks, we first list out related variables and notations that will be heavily used in our later derivations.Given anL-partite network G with Si being its i-th partite set and ni=Si being the number of nodes in Si, let Pik be the degree distribution of the nodes in Si. Denote Gij⊂G as the bipartite network consisting of partite sets Si and Sj with j=i−1,i+1. Let Pijk be the degree distribution of the nodes in Si⊂Gij that have connections with nodes in Si⊂Gij.Based on the definition of excess degree distribution, we, respectively, define the excess degree distributions ofPik and Pijk as PiEk and PijEk. Then, based on the definition of generating function, we define Gi0x=∑k=0∞xkPik and Gij0x=∑k=0∞xkPijk, respectively, as the generating functions for Pik and Pijk. Analogously, we define Gi1x=∑k=0∞xkPiEk and Gij1x=∑k=0∞xkPijEk, respectively, as the generating functions for PiEk and PijEk.


## 4.4. Percolation Theory Based on the Global Model

With all the above defined variables, for anL-partite networked system, we propose the following percolation theory for calculating Pi∞ with respect to the global model presented in Definition 6.Definition 8.
(probability vectoru). Consider the situation that 1−pi fraction of nodes is randomly removed from Si of an L-partite network G for ∀i∈1,L with pi∈0,1. For j∈i−1,i+1, define a probability vector u=u12,u21,…,uij,…,uL,L−1, with uij being the probability for a node in Si not to be connected to the LCC of G via a node in Sj.Theorem 1.
(percolation theory based on the global model). Consider anL-partite network G with L≥3; we randomly remove 1−pi fraction of nodes from Si for ∀i∈1,L with pi∈0,1. Based on the global model given in Definition 4, G reaches a stable stage. Define the probability vector u. In the limit of ni⟶∞, the fraction Pi∞ of nodes in Si that also belongs to the LCC in the stable stage of G is calculated as(14)P1∞=p11−G120u12,Pi∞=pi1−∏j=i−1,i+1Gij0uij,∀i∈2,L−1,PL∞=pL1−GL,L−10uL,L−1,with the variable uij∈u being calculated as(15)u21=1−p1+p1G121u12,uij=1−pj+pjGji1ujiGj,j+δ1uj,j+δ,uL−1,L=1−pL+pLGL,L−11uL,L−1,where δ=−1, if j=i−1, and δ=1, if j=i+1.Proof.
We start by consideringP1∞. As the probability for a node a∈S1 not to be connected to the LCC via a node b∈S2 is u12, the probability ϕ12 for nodes in S1 not to be connected to the LCC via nodes in S2 is calculated as(16)ϕ12=∑k=0n2P12ku12k.
In the limit ofni⟶∞, we have(17)limn2⟶∞ϕ12=∑k=0∞P12ku12k=G120u12.
Note that1−pi fraction of nodes is removed from Si for ∀i∈1,L; thus, pi fraction of nodes is remaining in Si. Therefore, in the LCC of G, the remaining fraction of nodes in S1 is calculated as(18)P1∞=p11−ϕ12=p11−G120u12.
Analogously, we can prove the correctness of the expression ofPL∞ as given in Theorem 1. Now, let us consider Pi∞.
Note that a nodea∈Si can simultaneously have neighbours in Si−1 and Si+1. If nodes in Si do not belong to the LCC, then the nodes in Si should not be connected to the LCC via their neighbours. Based on the above analysis, we know that the probability ϕi,i−1 for nodes in Si not to be connected to the LCC via nodes in Si−1 is(19)ϕi,i−1=∑k=0ni−1Pi,i−1kui,i−1k.
Analogously, the probabilityϕi,i+1 for nodes in Si not to be connected to the LCC via nodes in Si+1 is(20)ϕi,i+1=∑k=0ni+1Pi,i+1kui,i+1k.
Then, the probabilityϕi for nodes in Si not to be connected to the LCC via their neighbours is ϕi=ϕi,i−1⋅ϕi,i+1. Therefore, in the limit of ni⟶∞, we further have(21)limni⟶∞ϕi=Gi,i−10ui,i−1Gi,i+10ui,i+1,based on which we can figure out Pi∞ as(22)Pi∞=pi1−ϕi=pi1−Gi,i−10ui,i−1Gi,i+10ui,i+1.
To this end, the first part of Theorem1, i.e., the part regarding Pi∞, is proved. Next, we give the proof for the second part regarding the probability vector u.
We start by analyzingu21, which denotes the probability for the event that a node b∈S2 is not connected to the LCC of G via a node a∈S1 to happen. Note that if node a is removed, which happens with a probability 1−p1, then the above event obviously happens. Now, consider the situation that node a is not removed. Then, the aforementioned event happens if a is not connected to the LCC via its neighbours. As a consequence, in the limit of ni⟶∞, we have(23)u21=1−p1+p1∑k=0n2P12Eku12k=1−p1+p1⋅G121u12.
Analogously, we can prove the correctness of the expression ofuL−1,L. Next, we consider uij with j=i+1.
Note that nodes inSi have connections with nodes in Sj. The event that a node a∈Si is not connected to the LCC via a node b∈Sj, which happens with the probability uij, can happen under two situations: (S1) node b has been removed; (S2) node b is not removed and b itself is not connected to the LCC via its own neighbours. Situation S1 happens with the probability ψS1=1−pj. Thus, the key step for working out uij then lies in the calculation of the probability ψS2 for situation S2 to happen.
Because a nodeb∈Sj can simultaneously have neighbours in Si and Sj+1, if b is not connected to the LCC via its neighbours, then b should neither be connected to the LCC via nodes in Si nor via nodes in Sj+1. Assume that node b has k neighbours in Si; then, the probability φji for node b not to be connected to the LCC via nodes in Si is(24)φji=ujik.
Analogously, when nodeb has k neighbours in Sj+1, the probability φj,j+1 for node b not to be connected to the LCC via nodes in Sj+1 is(25)φj,j+1=uj,j+1k.
Recall the definition of excess degree distribution; the probabilities for nodeb to, respectively, have k neighbours in Si and k neighbours in Sj+1 are PjiEk and Pj,j+1Ek. As a consequence, the probability ψS2 can be calculated as(26)ψS2=pj∑k=0niPjiEkφji∑k=0nj+1Pj,j+1Ekφj,j+1.
Note that situations S1 and S2 are two independent events; therefore, in the limit ofni⟶∞, the probability uij is calculated as(27)uij=ψS1+ψS2=1−pj+pjGji1ujiGj,j+11uj,j+1.
The proof ofuij for j=i−1 is omitted as it is analogous to that of uij for j=i+1 as presented above. To this end, Theorem 1 is proved.Remark 5.
Note that when analyzingψS2, it is easy to derive the wrong expression of ψS2 in the following way:(28)ψS2=pj∑k=0∞PjEk∑m=0kkmujimuj,j+1k−m=pjGj1uji+uj,j+1.
The idea of the above derivations is thatm out of k neighbours of a node b∈Sj are not connected to the LCC via nodes in Si, and the remaining k−m neighbours of b are not connected to the LCC via nodes in Sj+1. However, the event that node b has k neighbours in Si and the event that node b has k neighbours in Sj+1 are independent. Therefore, variable m does not need to run over k for k∈0,∞.Remark 6.
From Theorem1, one can easily derive the percolation theory for L-partite networked systems with L=2, i.e., bipartite networked systems. Specifically, one can have(29)P1∞=p11−G120u12,P2∞=p21−G210u21,with u12 and u21, respectively, being calculated as(30)u12=1−p2+p2G211u21,u21=1−p1+p1G121u12.


## 4.5. Percolation Theory Based on the Local Model

When calculating the LCC, the global model takes a multipartite network as a whole while the local model by contrast analyzes its subnetworks. The local model requires that the final LCC should encompass nodes from every partite set. Therefore, the above proposed percolation theory does not work for multipartite networked systems with respect to the local model. In what follows we elucidate our proposed percolation theory based on the local model.Theorem 2.
(percolation theory based on the local model). Consider anL-partite network G with L≥3; we randomly remove 1−pi fraction of nodes from Si for ∀i∈1,L with pi∈0,1. Based on the local model given in Definition 5, G reaches a stable stage. Define the probability vector u. In the limit of ni⟶∞, the fraction Pi∞ of nodes in Si which also belongs to the LCC in the stable stage of G is calculated as(31)P1∞=p11−G120u12,Pi∞=pi∏j=i−1,i+11−Gij0uij,i∈2,L−1,PL∞=pL1−GL,L−10uL,L−1,with the variable uij being calculated as(32)u21=1−p1+p1G121u12,uij=1−pj1−Gji1uji1−Gj,j+δ1uj,j+δ,uL−1,L=1−pL+pLGL,L−11uL,L−1,where δ=−1, if j=i−1, and δ=1, if j=i+1.Proof.
We only present the proof forPi∞, since the proofs for P1∞ and PL∞ are exactly the same as that presented in Theorem 1. As mentioned earlier, a node a∈Si can simultaneously have neighbours in Si−1 and Si+1. Based on the local model given in Definition 5, we see that as long as there exists one neighbour of node a that connects a to the LCC, then node a definitely belongs to the LCC. According to the proof of Theorem 1, we know that in the limit of ni⟶∞, the probability ϕi,i−1 for nodes in Si not to be connected to the LCC via nodes in Si−1 is(33)ϕi,i−1=Gi,i−10ui,i−1.
Analogously, we haveϕi,i+1=Gi,i+10ui,i+1. Therefore, the probability for node a to be connected to the LCC via at least one neighbour in Si−1 is 1−ϕi,i−1. Analogously, the probability for node a to be connected to the LCC via at least one neighbour in Si+1 is 1−ϕi,i+1. Consequently, the probability ϕi¯ for nodes in Si to be connected to the LCC via their neighbours is calculated as(34)ϕi¯=1−ϕi=1−ϕi,i−11−ϕi,i+1.
Therefore, in the limit ofni⟶∞, Pi∞ is calculated as(35)Pi∞=piϕi¯=pi1−ϕi,i−11−ϕi,i+1=pi∏j=i−1,i+11−Gij0uij.
To this end, the correctness ofPi∞ as given in Theorem 2 is proved. Next, we give the proof for the probability variable uij. The proofs for variables u21 and uL−1,L are omitted as they are the same as that given in the proof for Theorem 1. We first analyze uij with j=i+1.
Recall that the variableuij denotes the probability that a node a∈Si is not connected to the LCC via a node b∈Sj. Analogous to what are analyzed in the proof for Theorem 1, the event that a∈Si is not connected to the LCC via b∈Sj also happens under two situations: (S1) node b is removed, which happens with the probability ψS1=1−pj; (S2) b remains and b is not connected to the LCC via its neighbours. Note that the probability ψS2 for situation S2 to happen cannot be calculated in the way demonstrated in the proof of Theorem 1. The reason is that the local model requires that the LCC contains nodes from Si for ∀i∈1,L, while the global model does not require this condition.
Because nodeb∈Sj has neighbours in Si and Sj+1, the probabilities φji and φj,j+1 are, respectively, calculated as φji=ujik and φj,j+1=uj,j+1k. Therefore, the probability φj for b∈Sj neither to be connected to the LCC via neighbours in Si nor via nodes in Sj+1 is(36)φi=∑k=0niPjiEkφji+∑k=0nj+1Pj,j+1Ekφj,j+1−∑k=0niPjiEkφji∑k=0nj+1Pj,j+1Ekφj,j+1.
In the limit ofni⟶∞, φi can be further calculated as(37)limni⟶∞φi=Gji1uji+Gj,j+11uj,j+1−Gji1ujiGj,j+11uj,j+1.
AsψS2=pjφi, in the limit of ni⟶∞, the probability uij is calculated as(38)uij=ψS1+ψS2=1−pj+pjφi=1−pj1−Gji1uji1−Gj,j+11uj,j+1.
Based on the same token shown above, we can work outuij for j=i−1 as(39)uij=1−pj1−Gji1uji1−Gj,j−11uj,j−1,and therefore Theorem 2 is proved.


## 5. Numerical Simulations

### 5.1. Random Multipartite Networks

The proposed theories exhausted in Section4 theoretically investigate the robustness of multipartite networks with arbitrary degree distributions in face of random node failures. Here we generate multipartite networks with Poisson degree distributions to validate the correctness of the proposed theories. The reasons for doing so are twofold. First, generating multipartite networks with Poisson degree distributions is easy to implement. Second, a Poisson distribution has very good mathematical properties. To be specific, for a Poisson distribution Pk=e−kkk/k! with k being its expectation, it is easy to prove that(40)G0x=∑k=0∞xkPk=∑k=0∞xke−kkkk!=ekx−1,(41)G1x=G0′xG0′1=ekx−1=G0x.Given an emptyL-partite network G, for all i∈1,L−1, we construct G by connecting each pair of nodes with one from Si and the other one from Si+1 with a predefined probability ri=di/N, where di is a constant. Then, it is easy to figure out that the degree distributions Pijk and Pjik for nodes in Si,Sj⊂Gij comply with the following Poisson distributions:(42)Pijk=njkrik1−rinj−k≈e−kijkijkk!,(43)Pjik=nikrik1−rini−k≈e−kjikjikk!,where kij=njri=nj⋅di/N and kji=nirj=ni⋅di/N.


### 5.2. Validation for Theorem1

Without loss of generality, in the simulations, we considerL-partite networks with L=3, i.e., tripartite networks. For a tripartite network G generated in the way illustrated in the previous section, when 1−pi fraction of nodes is randomly removed from Si⊂G for all i∈1,3 and the cascading failures propagate on G based on the defined global model, then Theorem 1 leads to the following simplified equations:(44)P1∞=p11−ek12u12−1,P2∞=p21−ek23u23−1ek21u21−1,P3∞=p31−ek32u32−1,(45)u21=1−p1+p1ek12u12−1,u23=1−p3+p3ek32u32−1,u12=1−p2+p2ek23u23−1ek21u21−1,u32=1−p2+p2ek23u23−1ek21u21−1.For simplicity, in the simulations, we set the parameters of a tripartite network to ben1=n2=n3=5×104, d1=d2=d, and d=3,6,9,12,15. As a consequence, we have k12=k21=k23=k32=k=d/3.Because the parameterpi affects the robustness of multipartite networks, in order to better demonstrate the simulation results, here we consider two simple cases: (C1) p1=p2=p3=p, i.e., we randomly remove the same fraction of nodes from each partite set; (C2) p1=p, p2=p3=1, i.e., we only remove nodes from partite set S1.Under case 1, the critical valuepc becomes(46)pc=1k23k32+k21k12.Under case 2, the critical valuepc=0. Interested readers are encouraged to discover this conclusion by themselves.Figure6 shows the simulation and theoretical results on the robustness of tripartite networks based on the global model. The theoretical results shown in Figure 6 are obtained by solving equations (44) and (45). During the simulations, p ranges from 0 to 1 at an interval of 0.025. It can be clearly seen from Figure 6 that the theoretical results coincide quite well with the simulations. Under case 1, the critical value pc given in equation (46) has the simplified form of pc=3/2d. Under case 2, pc=0, which indicates that the focal networks are extremely robust to random node failures. It can be observed from Figure 6 that the values of pc are in accordance with that of the simulations. The results shown in Figure 6 indicate that multipartite networks are robust to node failures when the global model is of concern.Figure 6
Robustness of tripartite networks based on the global model. Lines denote the theoretical results while symbols represent the simulation results. The first and second rows of the figure, respectively, represent the case that the node removal occurs toSi for all i∈1,3 and for i=1. Simulation results are averaged over 1000 trials.
(a)(b)(c)(d)(e)(f)


### 5.3. Validation for Theorem2

For a tripartite network with Poisson degree distributions, Theorem2 leads to the following simplified equations:(47)P1∞=p11−ek12u12−1,P2∞=p21−ek23u23−11−ek21u21−1,P3∞=p31−ek32u32−1,(48)u21=1−p1+p1ek12u12−1,u23=1−p3+p3ek32u32−1,u12=u32=1−p2+p2ek23u23−1+ek21u21−1−ek23u23−1ek21u21−1.Figure7 shows the simulation and theoretical results on the robustness of tripartite networks based on the local model. The theoretical results shown in Figure 7 are obtained by solving equations (47) and (48) with the same parameter settings presented in the previous section. The results recorded in Figure 7 also demonstrate that the proposed theory coincides quite well with the simulations.Figure 7
Robustness of tripartite networks based on the local model. Lines denote the theoretical results while symbols represent the simulation results. The first and second rows of the figure, respectively, represent the case that the node removal occurs toSi for all i∈1,3 and for i=1. Simulation results are averaged over 1000 trials.
(a)(b)(c)(d)(e)(f)By comparing Figures6 and 7, we can see that the robustness of multipartite networks with respect to the local model shows first-order phase transition, which indicates that multipartite networks with the local model are vulnerable to perturbations. Both Figures 6 and 7 show that larger mean degrees will enhance the networks’ robustness.


## 5.1. Random Multipartite Networks

The proposed theories exhausted in Section4 theoretically investigate the robustness of multipartite networks with arbitrary degree distributions in face of random node failures. Here we generate multipartite networks with Poisson degree distributions to validate the correctness of the proposed theories. The reasons for doing so are twofold. First, generating multipartite networks with Poisson degree distributions is easy to implement. Second, a Poisson distribution has very good mathematical properties. To be specific, for a Poisson distribution Pk=e−kkk/k! with k being its expectation, it is easy to prove that(40)G0x=∑k=0∞xkPk=∑k=0∞xke−kkkk!=ekx−1,(41)G1x=G0′xG0′1=ekx−1=G0x.Given an emptyL-partite network G, for all i∈1,L−1, we construct G by connecting each pair of nodes with one from Si and the other one from Si+1 with a predefined probability ri=di/N, where di is a constant. Then, it is easy to figure out that the degree distributions Pijk and Pjik for nodes in Si,Sj⊂Gij comply with the following Poisson distributions:(42)Pijk=njkrik1−rinj−k≈e−kijkijkk!,(43)Pjik=nikrik1−rini−k≈e−kjikjikk!,where kij=njri=nj⋅di/N and kji=nirj=ni⋅di/N.


## 5.2. Validation for Theorem1

Without loss of generality, in the simulations, we considerL-partite networks with L=3, i.e., tripartite networks. For a tripartite network G generated in the way illustrated in the previous section, when 1−pi fraction of nodes is randomly removed from Si⊂G for all i∈1,3 and the cascading failures propagate on G based on the defined global model, then Theorem 1 leads to the following simplified equations:(44)P1∞=p11−ek12u12−1,P2∞=p21−ek23u23−1ek21u21−1,P3∞=p31−ek32u32−1,(45)u21=1−p1+p1ek12u12−1,u23=1−p3+p3ek32u32−1,u12=1−p2+p2ek23u23−1ek21u21−1,u32=1−p2+p2ek23u23−1ek21u21−1.For simplicity, in the simulations, we set the parameters of a tripartite network to ben1=n2=n3=5×104, d1=d2=d, and d=3,6,9,12,15. As a consequence, we have k12=k21=k23=k32=k=d/3.Because the parameterpi affects the robustness of multipartite networks, in order to better demonstrate the simulation results, here we consider two simple cases: (C1) p1=p2=p3=p, i.e., we randomly remove the same fraction of nodes from each partite set; (C2) p1=p, p2=p3=1, i.e., we only remove nodes from partite set S1.Under case 1, the critical valuepc becomes(46)pc=1k23k32+k21k12.Under case 2, the critical valuepc=0. Interested readers are encouraged to discover this conclusion by themselves.Figure6 shows the simulation and theoretical results on the robustness of tripartite networks based on the global model. The theoretical results shown in Figure 6 are obtained by solving equations (44) and (45). During the simulations, p ranges from 0 to 1 at an interval of 0.025. It can be clearly seen from Figure 6 that the theoretical results coincide quite well with the simulations. Under case 1, the critical value pc given in equation (46) has the simplified form of pc=3/2d. Under case 2, pc=0, which indicates that the focal networks are extremely robust to random node failures. It can be observed from Figure 6 that the values of pc are in accordance with that of the simulations. The results shown in Figure 6 indicate that multipartite networks are robust to node failures when the global model is of concern.Figure 6
Robustness of tripartite networks based on the global model. Lines denote the theoretical results while symbols represent the simulation results. The first and second rows of the figure, respectively, represent the case that the node removal occurs toSi for all i∈1,3 and for i=1. Simulation results are averaged over 1000 trials.
(a)(b)(c)(d)(e)(f)


## 5.3. Validation for Theorem2

For a tripartite network with Poisson degree distributions, Theorem2 leads to the following simplified equations:(47)P1∞=p11−ek12u12−1,P2∞=p21−ek23u23−11−ek21u21−1,P3∞=p31−ek32u32−1,(48)u21=1−p1+p1ek12u12−1,u23=1−p3+p3ek32u32−1,u12=u32=1−p2+p2ek23u23−1+ek21u21−1−ek23u23−1ek21u21−1.Figure7 shows the simulation and theoretical results on the robustness of tripartite networks based on the local model. The theoretical results shown in Figure 7 are obtained by solving equations (47) and (48) with the same parameter settings presented in the previous section. The results recorded in Figure 7 also demonstrate that the proposed theory coincides quite well with the simulations.Figure 7
Robustness of tripartite networks based on the local model. Lines denote the theoretical results while symbols represent the simulation results. The first and second rows of the figure, respectively, represent the case that the node removal occurs toSi for all i∈1,3 and for i=1. Simulation results are averaged over 1000 trials.
(a)(b)(c)(d)(e)(f)By comparing Figures6 and 7, we can see that the robustness of multipartite networks with respect to the local model shows first-order phase transition, which indicates that multipartite networks with the local model are vulnerable to perturbations. Both Figures 6 and 7 show that larger mean degrees will enhance the networks’ robustness.


## 6. Conclusion

Investigating the robustness of complex systems under perturbations is pivotal. Network robustness analysis provides a potent instrument towards that purpose. While the majority of existing studies on network robustness analysis focus on multilayer networked systems, this paper theoretically studied the robustness of multipartite networked systems. This paper first established two network models for depicting the cascading failures on multipartite networked systems in face of node failures. Equipped with the established network models together with the largest connected component concept, this paper then developed the corresponding percolation theories for analyzing the robustness of multipartite networked systems under random node failures. The proposed theories uncovered the second-order and first-order phase transition phenomena on the robustness of multipartite networked systems. The correctness of the proposed theories had been validated through simulations on multipartite networks with Poisson degree distributions.Note that complex systems in reality can suffer from target attacks. Although this paper only investigates the robustness of multipartite networked systems under random perturbations, the proposed models and theories provide scientific insights for the target attack scenarios. Meanwhile, the proposed theories could shed new lights on the optimal structure design of robustness network and/or networked systems.



---

*Source: 3974503-2020-05-20.xml*