# Immunization of Cooperative Spreading Dynamics on Complex Networks

Authors: Jun Wang; Shi-Min Cai; Tao Zhou
Journal: Complexity
 (2021)

---

## Abstract

Cooperative spreading dynamics on complex networks is a hot topic in the field of network science. In this paper, we propose a strategy to immunize some nodes based on their degrees. The immunized nodes disable the synergistic effect of cooperative spreading dynamics. We also develop a generalized percolation theory to study the final state of the spreading dynamics. By using the Monte Carlo method, numerical simulations reveal that immunizing nodes with a large degree cannot always be beneficial for containing cooperative spreading. For small values of transmission probability, immunizing hubs can suppress the spreading, while the opposite situation happens for large values of transmission probability. Furthermore, numerical simulations show that immunizing hubs increase the cost of the system. Finally, all numerical simulations can be well predicted by the generalized percolation theory.


---

## Body

## 1. Introduction

Many real-world phenomena in social and biological systems (e.g., information diffusion and epidemic spreading) can be described as spreading dynamics on complex networks [1, 2]. Historically, according to the number of dynamics, the spread on complex networks experienced two periods. The first period is single spreading dynamics on complex networks, where there is only one dynamics on the network. Romualdo and Vespignani are the first to study the single spreading dynamics on complex networks with heterogeneous degree distribution [3, 4]. They revealed that the epidemic threshold vanishes if the heterogeneity of degree distribution is strong enough. The second period is coevolving spreading dynamics that more than one dynamics are evolving in the system [5, 6]. According to the interacting mechanisms between different spreading dynamics, we can divide into competing, asymmetric, and cooperative spreading dynamics.The competing spreading dynamics is used to describe two competing hosts. For successively competing spreading dynamics of two epidemics, Newman [7] found that the second epidemic threshold is always larger than the first one. Brian and Newman Mark [8] further adopted a competing percolation theory to reveal the phase diagram of competing spreading dynamics of two epidemics and found that the faster spreading epidemic is dominant. Recently, more works focus on the competing spreading dynamics on overlay and multiplex networks [9–11].The asymmetric spreading dynamics is widely used to describe the coevolving spreading of awareness and epidemic. It shows an asymmetric interaction, the dynamicsa suppresses the dynamics b, while the dynamics b promotes the dynamics a. Granell et al. found that the diffusion of awareness significantly suppresses the epidemic spreading for reversible coevolving spreading [12, 13]. Wang et al. found that the interlayer degree correlation is beneficial for containing epidemic spreading, and there is an optimal information diffusion rate to suppress the epidemic spreading [14, 15].The cooperative spreading dynamics suggests that the dynamicsa and b promote each other. A significant result revealed by Cai et al. is that the phase transition may be discontinuous if the cooperative strength is large enough [16]. Chen et al. further investigated the effects of network structures and dimensions on the phase diagram of cooperative spreading dynamics [17–19].The immunization of spreading dynamics on complex networks is a hot topic. Some successful strategies have been proposed, such as targeted immunization, acquaintance immunization, and information spreading-based immunization [20–26]. To our best knowledge, there is still lack of systematic study on immunization of cooperative spreading dynamics on complex networks. In this paper, we propose an immunization strategy and use generalized percolation theory to study the final state of the two dynamics cooperatively spreading on scale-free (SF) random networks. The extensive numerical simulations are performed to verify the correctness and effectiveness of our proposed strategy.


## 2. Model Descriptions

This section introduces the immunization strategy for the cooperative spreading dynamics on complex networks. We consider a network with sizeN. Its degree distribution is Pk. We construct the network by applying the uncorrelated configuration model [27]. To introduce the immunization strategy, we assign each node with an immunization probability. We suppose that the immunization probability of each node is affected by its surrounding environment. In the network, we consider the surrounding environment with the number of neighbors of the node. Denoting Wki as the probability of node i with degree ki that does not be immunized, Wki can be expressed as(1)Wki=kiα∑jkjα,−∞<α<+∞,where α is a hyperparameter. For α=0, every node is immunized with the same probability. When α⟶+∞, nodes with a small degree have a large immunization probability; the opposite situation happens when α⟶−∞. We select the fraction 1−p of nodes in the network according to equation (1) and immunize them. If a node is immunized, the synergistic effect of two dynamics is disabled for the cooperative spreading dynamics on complex networks.The epidemics (i.e., specific dynamics)a and b spread on the network following the susceptible-infected-recovered (SIR) model. At any time, each node can exist in one of the three states of each epidemic: susceptible (S), infected (I), and recovered (R). In the susceptible state, a node is susceptible and has not been infected. In the infected state, a node is infected by the epidemics x∈a,b and can transmit the epidemics to its neighbors in the network. The recovered state indicates that a node has recovered from the epidemics and will not be infected again. For the coinfection epidemic spreading, the state of a node can be divided into nine types denoted as SaSb, SaIb, SaRb, IaSb, IaIb, IaRb, RaSb, RaIb, and RaRb.In the process of the spreading of the two epidemics, we randomly select a seed node in the network for the epidemicsa and b. For a node that does not be infected by any epidemic, it will be infected by the epidemic a(b) with probability 1−1−λka (with probability 1−1−λkb), where λ is the infection probability of the epidemics a and b. The parameter ka(kb) represents the number of infected neighbors in the network of the epidemic a(b). If a node i is infected by one of the two epidemics, there are two situations. On the one hand, if node i does not be immunized, it will be infected by the other epidemic with probability 1−1−ϑkx, where kx is the number of infected nodes by the epidemic x∈a,b. To include the synergistic effect to the spreading dynamics, we assume ϑ>λ. On the other hand, if node i is immunized, it will be infected by the other epidemic with probability 1−1−λkx. Each infected node recovers with probability γ. The cooperative spreading dynamics evolves until there are no nodes in the infected state.In reality, immunizing a node usually costs some resources. In our model, we consider nodei with degree k paying the immunizing cost as kc1 when it is immunized. The c1 is the cost unit. The recovery of infected nodes also needs some resources. If node i with degree k is infected by the epidemic a(b), we consider that its recovery cost is kca(kcb), where ca(cb) represents the cost unit. Moreover, if node i is not infected with any disease, it does not need to pay any recovery cost. Therefore, the overall cost of node i with degree k is(2)Ck=Icc1+Iaca+Ibcbk,where Ia,b,c∈0,1. Ic indicates whether node i is immunized. Ia(Ib) indicates whether node i is infected by the epidemic a(b). The mean cost of all nodes in the network is(3)C=∑kPkCk.


## 3. Theoretical Analysis

Previous studies revealed that the final outbreak size of the SIR model could be mapped to solving the giant connection cluster (GCC) of bond percolation process [28–30]. To get the final outbreak size of the epidemics a and b simultaneously, we develop a generalized bond percolation theory inspired by Refs. [31, 32]. As we know, the generating function of a network with degree distribution Pk can be wrote as Gx=∑kPkxk. To get the GCC, we define μa(μb) as the probability, that is, a randomly selected edge connecting to a node in the GCC infected by the epidemic a (b).Next, we need to write down the self-consistent equation forμa and μb by considering whether a node is immunized. Firstly, we analyze diseases a and b separately. If node i is infected by the epidemic a with no coinfection, i.e., node i in the GCC of the epidemic a with no coinfection, the probability is νaλ=1−1−λμak−1. Contrarily, if node i is infected by the epidemic a with coinfection, the probability is νaϑ=1−1−ϑμak−1. For the epidemic b, we can get the same equations, νbλ=1−1−λμbk−1 and νbϑ=1−1−ϑμbk−1. Then, we consider the synergistic effect of the epidemics a and b. If node i is in the GCC of the epidemic a, there are two situations. First, node i is only infected by the epidemic a with probability νaλ1−λμbk. Second, node i is infected by the two epidemics. There are three subdivisions. (i) If node i is immunized with probability 1−ℓk, there is no coinfection. It is infected by the two epidemics with probability νaλ1−λμbνbλ+λμb. ℓk is the probability that node i with degree k does not be immunized. (ii) The node i is not immunized with probability ℓk, and there may be coinfection. If the coinfection happens in the epidemic a, in other words, node i is infected by the epidemic b first and then reinfected by the epidemic a; the probability is ℓkνaϑ1−λμbνbλ+λμbs. (iii) If the coinfection happens in disease b, the probability is ℓkνaλ1−ϑμbνbϑ+ϑμb1−s. The parameter s is the probability that node i is first infected by the epidemic b and reinfected by the epidemic a. That is, s is corrected to the transmission rate of the two epidemics. Considering the abovementioned situations, we have(4)μa=∑kkPkk1−ℓkνaλ1−λμbνbλ+λμb+νaλ1−λμbk+ℓkℓkνaϑ1−λμbνbλ+λμbs+ℓkνaλ1−ϑμbνbϑ+ϑμa1−s.By usingGx, we rewrite equation (4) as(5)μa=1−1−ℓksG11−λμa+1−λμbℓk1−sG11−λμb−ℓkG11−λμa⋅1−λμb−ℓksG11−ϑμa−1−λμbG11−ϑμa⋅1−λμb−ℓk1−s1−ϑμbG11−ϑμb−G11−λμa⋅1−ϑμb,where G1x=G′x/G′1=1/k∑kkPkxk−1 is the generating function for the excess degree distribution of the network. Similarity, we can get the μb as(6)μb=1−1−ℓk+ℓksG11−λμb+1−λμaℓksG11−λμa−ℓkG11−λμa⋅1−λμb−ℓks1−ϑμaG11−ϑμb−G11−ϑμa⋅1−λμb−ℓk1−sG11−ϑμb−1−λμaG11−λμa⋅1−ϑμb.Note that the value ofℓk is still unknown in equations (5) and (6). We will solve it inspired by Refs. [33, 34]. Defining Afk as the number of immunized nodes with degree k and Pfk as the degree distribution in the residual network, in which all nodes are immunized, here, f is the current fraction of immunized nodes. We get(7)Pfk=AfkfN.Once another node is assigned without immunization according to equation (1), Afk changes as(8)Af−1/Nk=Afk−Pfkkαkαf,where kαf=∑kPfkkα. In the limit N⟶∞, equation (8) can be presented in terms of derivative of Apk with respect to p,(9)dAfkdf≈NPfkkαkαf.Differentiating equation (7) with respect to dAfk/df≈NPfkkα/kαf and using equation (9), we obtain(10)−fdPfkdp=Pfk−Pfkkαkαf.DefineHαg=∑kPkgkα, and let g=Hα−1f. We find by direct differentiation that(11)Pfk=PkHαggkα=1fPkgkα,(12)kαf=gHα′gHαg.We iterate these equations untilf=1−p. By using equation (11), the probability ℓk is that a node with degree k without immunization is ℓk=1−Pfk.Inserting the value ofℓk into equations (5) and (6), we obtain the probabilities μa and μb. We can further get the coinfection outbreak size of two epidemics denoted as Pab. If node i is in the GCC of the epidemics a and b simultaneously, it must be infected with the two epidemics. There are three possible situations. (i) 1−ℓk1−λμaνaλ+λμa1−λμbνbλ+λμb means node i is immunized and infected by the epidemics a and b independently. (ii) ℓks1−ϑμaνaϑ+ϑμa1−λμbνbλ+λμb means node i without immunization, and first is infected by the epidemic b and reinfected by the epidemic a. (iii) ℓk1−s1−λμaνaλ+λμa1−ϑμbνbϑ+ϑμb means node i without immunization, and first is infected by the epidemic a and reinfected by the epidemic b. We obtain(13)Pab=∑kPk1−ℓk1−λμaνaλ+λμa1−λμbνbλ+λμb+ℓk1−ϑμaνaϑ+ϑμa1−λμbνbλ+λμbs+1−λμaνaλ+λμa1−ϑμbνbϑ+ϑμb1−s.By usingGX, we can transform equation (13) into(14)Pab=1−1−ℓk+ℓksG11−λμb−1−ℓksG11−λμa++1−ℓkG11−λμa⋅1−λμb−ℓksG11−ϑμa−G11−ϑμa⋅1−λμb−ℓk1−sG11−ϑμb−G11−λμa⋅1−ϑμb.When we get the nodes which infected with the epidemicsa and b, we can get the mean cost of all nodes in the network as(15)C=∑kPk1−ℓkc1k+Pakcak+Pbkcbk,where Pak is the probability that a node with degree k is infected with the epidemic a. Similarity, Pbk is the probability for the epidemic b. Similar to equation (13), the Pak is(16)Pak=1−ℓk1−λμaνaλ+λμa1−λμbνbλ+λμb+ℓk1−ϑμaνaϑ+ϑμa1−λμbνbλ+λμbs+1−λμaνaλ+λμa1−ϑμbνbϑ+ϑμb1−s+1−λμaνaλ+λμa1−λμbk,and Pbk is(17)Pbk=1−ℓk1−λμaνaλ+λμa1−λμbνbλ+λμb+ℓk1−ϑμaνaϑ+ϑμa1−λμbνbλ+λμbs+1−λμaνaλ+λμa1−ϑμbνbϑ+ϑμb1−s+1−λμbνbλ+λμb1−λμak.Considering all possible values ofk, we obtain the probability of the fraction of nodes infected by the epidemics a and b as(18)Pa=∑kPkPak,Pb=∑kPkPbk,respectively.Another important question is that when the two epidemics will globally outbreak? Taking the epidemica as an example, in the bond percolation theory, equation (5) always has a trivial solution of ua=0. When there is a nontrivial solution, μa<1 indicates a global outbreaks. To determine the value of outbreak threshold λc, we rewrite equations (5) and (6) inspired by Ref. [35],(19)Faμa,μb=μa−faμa,μb=0,Fbμa,μb=μb−fbμA,μB=0,respectively, where faμa,μb and fbμa,μb, respectively, represent the right hands of equations (5) and (6). At the point of outbreak threshold λc, the following condition(20)∂faμa,μb∂μb∂fbμa,μb∂μa|λ=λc=1,is fulfilled. By numerically solving equation (20), we can obtain the outbreak threshold λc.


## 4. Results

In this section, we study the cooperative spreading dynamics of two epidemics on SF random networks. Specifically, we set the SF random network with power-law degree distributionPk∼k−γA, where γA represents the degree exponent. The smaller the γA, the stronger the heterogeneity of degree distribution will be. In our model, we set c1=ca=cb=1 to include the immunization cost of a node and the recovery cost of an infected node, s=0.5, by assuming an equal transmission rate of the epidemics a and b, and the recovery probability γ=1. All numerical simulations are averaged over 100 times.In Figure1, we study the cooperate epidemic spreading on a SF random network with different p and α. We set ϑ=0.99 and γA=2.7. When we fix p=0.5, that is, fixing the number of unimmunized nodes, the outbreak threshold increases with the decreasing α. As the propagation probability λ increases, the propagation range increases. The reason is that when α is large, the synergy acts on the nodes with a large degree. These nodes are more likely to be infected preferentially, so that the epidemics will be more likely to break out under the coinfection. When the α is small, the synergy acts on the nodes with a small degree. At this time, the coinfection leads to a large outbreak size. When we fix α=3, p=0.2 and p=0.5 have the same outbreak threshold. Importantly, we find that immunizing large degree nodes suppresses the cooperate epidemic spreading when λ is small, while promoting the spreading when λ is large. We explain the phenomenon as follows. The hubs are easy to be infected for any values of λ. If the epidemic a infects the hubs first, the epidemic b can hardly infect them when immunizing large degree nodes (e.g., α=−3) and λ is small. As a result, the epidemic spreading size decreases. When λ is large, the epidemic b can infect the nodes with small degrees. As those small degree nodes have synergistic effect, the epidemic spreading is promoted.Figure 1
The coinfection outbreak size of the epidemica (a), epidemic b (b), and two epidemics (c) versus the spreading probability λ with different p and α. The inset panels enlarge the results when λ is small. We set ϑ=0.99 and the SF random network with N=104, k=10, and γA=2.7.We further investigate the effects of the heterogeneity of degree distribution on the epidemic spreading in Figure2. We set ϑ=0.99, p=0.5, and α=3. On the one hand, we find that strong heterogeneity of degree distribution decreases the global outbreak threshold of the epidemics because of the existence of some hubs. On the other hand, we find that Pa, Pb, and Pab decrease with the decreasing γA when λ is small while increases with γA when λ is large.Figure 2
The coinfection outbreak size of the epidemica (a), epidemic b (b), and two epidemics (c) versus the spreading probability λ with different γA. The inset panels enlarge the results when λ is small. We set p=0.5, α=3, and ϑ=0.99. The other parameter of SF random network is set to be N=104, k=10.Furthermore, we can see that the theoretical analysis well predicts the numerical simulation results in both Figures1 and 2. Note that the values of Pa and Pb are approximately equal since the two SF networks have the same statistical characteristic. However, the values of Pab are smaller than those of Pa and Pb because a node infected by two epidemics is more difficult than that infected by only one of them.Finally, we study the cost of cooperate epidemic spreading on SF random networks. In Figure3, we present the effectiveness of p and α on the mean cost C of all nodes versus the spreading probability λ. When we fix p=0.5 and c=1, the immunizing cost is large in α=−3. In this case, the synergy acts on the nodes with small degree. The immunizing cost of large degree nodes is also large. But with the λ increase, the outbreak size increases and the recovery cost increases. When λ≈0.06, the mean cost of all nodes is almost the same. When we fix α=3, with p increase, the immunizing cost decreases. The recovery cost of p=0.5 grows faster than the recovery cost of p=0.2.Figure 3
The mean costC of all nodes versus the spreading probability λ with different p and α. We set ϑ=0.99 and the SF random network with N=104, k=10, and γA=2.7.We further study the cost of cooperate epidemic spreading on SF random network with different degree distribution. As shown in Figure4, we can see that with the γA increase, the immunizing cost increases. The mean cost of all nodes decreases with γA for small values of λ and increases with γA for large values of λ. In addition, we can see that the theoretical analysis well predicts the numerical simulation results in both Figures 3 and 4.Figure 4
The mean costC of all nodes versus the spreading probability λ with different degree distribution. We set p=0.5, α=3, and ϑ=0.99. The other parameter of SF random network is set to be N=104, k=10.


## 5. Conclusion

In conclusion, we studied the immunization of cooperative spreading dynamics on complex networks. In our model, we assumed that the immunization probability depends on the degree of nodes. Furthermore, the cost of immunization correlated with node degrees. Using a generalized percolation theory, we theoretically analyzed the final outbreak size and the cost of system. Compared with immunizing small degree nodes, we found that immunization nodes with large degrees suppress the spreading for small values of transmission probability, while the opposite situation happens for large values of transmission probability. For the cost of the system, we revealed that, immunizing hubs increase the cost of the system. Finally, we investigated the effects of degree heterogeneity on final spreading size and cost of the system. Our results shed some light on studying the cooperative spreading dynamics and may provide some clues for future researches.



---

*Source: 6645113-2021-01-18.xml*