# An Immunization Strategy Based on Propagation Mechanism

Authors: Yixin Zhu; Fengli Zhang; Wenqiang Guo
Journal: Discrete Dynamics in Nature and Society
 (2014)

---

## Abstract

With the ubiquity of smart phones, wearable equipment,  and wireless sensors, the topologies of networks composed by them change along with time. The immunization strategies in which network immune nodes are chosen by analyzing the static aggregation network topologies have been challenged. The studies about interaction propagations between two pathogens show that the interaction can change propagation threshold and the final epidemic size of each other, which provides a new thinking of immunization method. The eradication or inhibition of the virus can be achieved through the spread of its opposite party. Here, we put forward an immunization strategy whose implementation does not depend on the analysis of network topology. The immunization agents are randomly placed on a few of individuals of network and spread out from these individuals on network in a propagation method. The immunization agents prevent virus infecting their habitat nodes with certain immune success rate. The analysis and simulation of evolution equation of the model show that immune propagation has a significant impact on the spread threshold and steady-state density of virus on a finite size of BA networks. Simulations on some real-world networks also suggest that the immunization strategy is feasible and effective.


---

## Body

## 1. Introduction

Every year, there are a lot of new viruses that appeared on the Internet and the Mobile Internet, which threaten not only the safety of networks and hosts, but also the information security of network users, including their accounts, passwords, confidentiality, and privacy. To inhibit the spread of viruses, a variety of immune strategies are put forward, such as target immunization, annular immunization, acquaintances immunization, local immunization, and first delete edge immunization [1–5]. An immunization strategy is often defined as the choice of a set of individuals who neither catch nor transmit the disease. The choice method is mainly based on the attributes of nodes in the network topology. However, it is not always effective and feasible to access and calculate properties of each node in order to pick out immune nodes in a large network. Wireless connection devices are ubiquitous in modern society, such as smart phones, wearable equipment, and wireless sensors. Various online social networks and services spring up on the Internet. The edges between nodes change along with time on these networks [6–8]. There is often a greater difference between the actual property values of network nodes and the topology attributes or dynamic attributes of network nodes computed on the basis of static aggregation networks.At the beginning of the 21st century, the worm Red Code had almost paralyzed the whole Internet by flooding a lot of useless packets [9]. Thereafter, there appeared a new worm called Green Code and its goal is to find and remove the worm Red Code. The worm Green Code also spread by means of flooding. Its harm is even more than its benefits, but it gives us a new idea about the inhibition method of the virus spread. Immunization agents and countermeasures [10, 11] can be spread just like viruses do. Immunization agent’s role is to inhibit the spread of virus, which can be seen as a competitive spread between good viruses and bad viruses.There are growing researches about dynamic interactions of multiple epidemics in recent years. The method of generating function was used by Newman et al. to study the competing epidemics of two kinds of virus agents, which promote or inhibit the spread of each other [12–14]. Bond percolation theory and the generating function method can exactly demonstrate the various attributes of the network structure and analyze the final size of the epidemic outbreak and epidemic threshold of virus. But they ignore the time evolution process during the outbreak. Another mathematical modeling method for theoretical analysis of infectious disease spread is the compartment model. It describes the time evolution of the epidemic and yet simplifies propagation model parameters. The studies of dynamic interaction between multiple pathogens spreading on overlay networks need to consider more factors such as joint degree distribution of overlapping nodes. Reference [15] adopts the bond percolation theory and [16] uses compartment method to model and analyze dynamic interaction of two pathogens on overlay networks. These models and analyses of their evolution equations are often more complex and difficult to be handled. Moreover, the interaction of two pathogens is not always symmetrical. The interaction model from [17] consists of two propagation particle species A and B, in which A induces B while B suppresses A. For another thing, the spread of infectious diseases tends to cause increasing awareness of individual about disease and changes of individual behavior [18–21]. The changes of individual consciousness and behavior make healthy people reduce their susceptibility about disease to avoid being infected and infected persons reduce their infectivity by self-imposed quarantine and practice of better hygiene, which shorten duration of infection and extend duration of immunity. In computer networks, the behavioral responses to computer virus from users are often shown as the alteration of user operation behaviors, for example, more willing to update the antivirus software and accept patches, avoiding clicking on strange suspicious links, and opening the strange spam.The immunization strategies whose implementations depend on the analysis of network global topology structure are difficult to quickly implement on the real-world networks. Here, we put forward a simple immunization strategy on the basis of interaction propagation of virus and immunization agent. The vaccine against a given virus or worm, namely, immunization agent, propagates on networks analogous to the spread behavior of virus. If an individual is infected by immunization agent and successfully obtain immunization, it will be free from infection by the virus, which curbs the spread of the virus, just like the inhibitory effect of the worm Green Code on the worm Red Code.


## 2. Model

When the virus is epidemic on the network, the immunization agent is placed on a random chosen node and begins to propagate on network, whose works are similar to that of the worm program in the computer network. The transmission way of immunization agent is designed for SIS (susceptible-infected-susceptible) propagation mode [22]. Based on the version of the SIS model, each individual belongs to either a susceptible (S) or infected (I) state at any given time. When a susceptible individual and an infected individual interact, the former may be infected by the latter at some infection rate.The immunization agent is transmitted in SIS mode rather than SI mode. First, the example of worm Green Code shows that its cost brought by excessive propagation (flood propagation mode) and complex function far exceeds the resulting revenue. Second, immunization is not permanent in many cases of reality. On a host, immunization programs are likely to be treated as malicious programs by a security software or conflict with some application software and therefore be shut down or even removed. Immune program itself may be out of order and unable to run. The host systems possibly collapse and are reinstalled. These make the host turn back to the susceptible state from the immune state. Finally, SI transmission mode is a special case of SIS transmission mode where the recovery rate is zero.Figure1 shows the state transition diagram of the immune model. Due to the influence of two kinds of spread agents, there are two spread state values on each node of the system at the same time. The spread states of any node i are denoted by (X(1),X(2))i, where the symbols X(1)and X(2) signify the spread state of virus and immunization agent, respectively.Figure 1
State transition diagram of the immune model.Immunization agents have two functions, namely, immune function and spread function. Immune function is that the immunization agents prevent successfully the transmission of the virus to the immunized nodes from their neighbors with probabilityδ at each time step. Spread function of immunization agent is described as follows. At each time step, each infected node by immunization agent propagates immunization agent in its neighbor nodes in probability α(2) and recover itself into a susceptible state in probability β(2). In fact, the spreading mode of immunization agents is the pure SIS spreading mode.As shown in Figure1, each node infected by the virus infects its neighbor nodes with transmission rates α(1) in each time step, but the infectious success rate for a neighbor node infected by immunization agent is only 1-δ. If the node i is the neighbor of node j and node j has been infected by virus, the node i has the following three situations in the spread of the virus.(1)
If the nodei is not infected by virus and immunization agent, the probability that the node i is infected by virus from its neighbor node j is α(1).(2)
If the nodei is not infected by virus but is infected by immunization agent, the probability that the node i is infected by virus from its neighbor node j is (1-δ)α(1).(3)
If the nodei is infected by virus, the probability that the node i recovers itself into a susceptible state is β(1) whether or not it is infected by immunization agents. Consider the following:
(1)(S,S)i+(I,*)j→α(1)(I,*)i+(*,*)j,(S,I)i+(I,*)j→(1-δ)α(1)(I,*)i+(*,*)j,(I,*)i→β(1)(S,*)i,where the symbol * represents S state or I state.If the nodej is a neighbor node of node i, the node i has the following two situations in the spread of immunization agent. Consider the following:
(2)(*,S)i+(*,I)j→α(2)(*,I)i+(*,*)j,(*,I)i→β(2)(*,S)i.The expressionρk(1)(t) and ρk(2)(t) denotes the infectious density of virus and immunization agents on nodes with degree k of network at time t, respectively. Then, 1-ρk(2)(t) is the probability that a node with degree k is not infected by immunization agent at time t. The expression (1-δ)ρk(2)(t) is the probability that a node with degree k is infected by immunization agent and immunized failure, which means that a node is infected by immunization agent that is unsuccessful to prevent invasion from virus. The combination of the above two probabilities equals 1-δρk(2)(t), which signifies the probability that a node with degree k of network is not immunized. Therefore, the evolution equation of virus propagation is obtained as
(3)dρk(1)(t)dt=α(1)k[1-ρk(1)(t)]×[1-δρk(2)(t)]θ(ρ(1)(t))-β(1)ρk(1)(t).The evolution equation of immunization agents spread is(4)dρk(2)(t)dt=α(2)k[1-ρk(2)(t)]θ(ρ(2)(t))-β(2)ρk(2)(t),
where
(5)θ(ρ(1)(t))=1<k>∫0∞kP(k)ρk(1)dk,(6)θ(ρ(2)(t))=1<k>∫0∞kP(k)ρk(2)dk.


## 3. Threshold Analysis on the BA Networks

When system reaches steady state, the left side of (4) equals zero. We can obtain the infectious density of immunization agents on nodes with degree k of network:
(7)ρk(2)=kλ2θ21+kλ2θ2.The symbolλ2=α2/β2 is the effective transmission rate of immune spread. Parameter θ2 is the abbreviation of the symbol θ(ρ(2)(t)) of (4), which is a function about λ2.In BA network withN nodes and m new edges of each node, its parameters can be obtained as follows [23]. The average degree of the network is 2m, minimum degree is m, maximum degree Kc equals mN1/2, and node degree probability distribution p(k) equals 2m2k-3/(1-N-1). Substituting the above parameters and (7) into (6), we obtain
(8)θ2=1-N-1/2e(1-N-1)/mλ2mλ2(e(1-N-1)/mλ2-1).When the spread of virus reaches steady state, we obtain by (3)
(9)ρk(1)=kλ1θ1(1-δρk(2))1+kλ1θ1(1-δρk(2)).The symbolλ1=α1/β1 is the effective transmission rate of virus spread. Parameter θ1 is the abbreviation of the symbol θ(ρ(1)(t)) of (3), which is a function about λ1 and λ2. Substituting the above parameters of finite size BA network and (9) into (5), we obtain
(10)θ1=1<k>∫mkcλ1k2P(k)[1+(1-δ)λ2θ2k]θ11+(λ1θ1+λ2θ2)k+(1-δ)λ1λ2θ1θ2k2dk.We define an auxiliary function as follows:(11)f(θ1)=1<k>×∫mkcλ1k2P(k)[1+(1-δ)λ2θ2k]θ11+(λ1θ1+λ2θ2)k+(1-δ)λ1λ2θ1θ2k2dk.-θ1Because the functionf(θ1) is convex,f′′(θ1)<0, f(0)=0, and f(1)<0, the sufficient and necessary condition that the equation f(θ1)=0 has nonzero solutions in the interval 0<θ1<1 is f′(0)>0. Consider the following:
(12)f′(0)=mλ11-N-1[12ln⁡N-δln⁡(1+λ2θ2mN1/21+λ2θ2m)]-1>0λ1>1-N-1m[12ln⁡N-δln⁡(1+λ2θ2mN1/21+λ2θ2m)]-1,(13)λ1C=1-N-1m[12ln⁡N-δln⁡(1+λ2θ2mN1/21+λ2θ2m)]-1.Under the influence of immune transmission, the virus spread threshold is(14)λC=max⁡{λSISC,λ1C},
where the symbol λSISC is the spread threshold of pure SIS transmission method in the finite size of BA networks. It satisfies
(15)λSISC=<k><k2>=2(1-N-1)mln⁡(N).As shown in Figure2, the virus spread threshold increases rapidly with the increase of immune success rate δ and effective transmission rate λ2 on the finite size of BA network. The greater the immune success rate δ is, the greater the increasing rate of virus spread threshold λC is. The propagation of virus can be completely ended by choosing the appropriate immune effective transmission rate λ2 and guaranteeing certain immune success rate δ on the finite size of BA networks.Figure 2
The virus spread thresholdλC as a function of the immune success rate δ on the finite size BA networks, for the different effective transmission rate λ2 of immunization agent. Network node number N=2000 and edge number from each new node m=5.When the immune success rate satisfiesδ=1 in particular, we obtain λ1C=λ2 by (8) and (13). Under this condition, threshold value of the virus spread λC equal to max⁡{λSISC,λ2} and (9) is written as
(16)ρk(1)=kλ1θ1(1-ρk(2))1+kλ1θ1(1-ρk(2)).Substituting parameters of the finite size of BA network and (16) into (5) we obtain
(17)θ1=1-N-1/2e(1-N-1)/mλ1-mλ2θ2(e(1-N-1)/mλ1-1)mλ1(e(1-N-1)/mλ1-1).The infectious density of the virus spread at steady state is(18)ρ(1)=∫mkcP(k)ρk(1)dk.Substituting parameters of the finite size of BA network and (16) into (18) we obtain
(19)ρ(1)=2mλ1θ11-N-1[1-N-1/2-mwln⁡(1+mwN-1/2+mw)],
where w=λ1θ1+λ2θ2. The parameters θ1 and θ2 can be obtained by (17) and (8), respectively.For a finite size BA of network with 2000 nodes and 5 new edges of each node, its propagation threshold for pure SIS method isλSISC≈0.0526. Figure 3 displays that the virus propagation threshold equals the immune effective transmission rate λ2, where λ2>λSISC and the infectious density of virus drops off with the augment of the immune effective transmission rate λ2. The above two points demonstrate that the immune effect is remarkable under the condition of immune success rate δ=1 on finite size of BA networks.Figure 3
The node densityρ(1) infected by virus as a function of virus effective transmission rate λ1, for the different effective transmission rate λ2 of immune agent, where δ=1. TV prefix figure legend item is theory analytical values calculated according to (19), and SV prefix figure legend item is corresponding simulation values. Network node number N=2000, new edge number from each nodem = 5, the recovery rate of the virus spread β(1)=0.001, and the recovery rate of the immune agent spread β(2)=0.01.


## 4. Empirical Tests on Real Networks

The first real-world network in our research is a snapshot of the Gnutella peer-to-peer file sharing network in August 6, 2002 [24, 25]. Nodes represent hosts in the Gnutella network topology and edges represent connections between the Gnutella hosts.Enron email communication network covers all the email communication within a dataset of around half million emails [26, 27]. This data was originally made public and posted to the web by the Federal Energy Regulatory Commission during its investigation. Nodes of the network are email addresses and if an address i sent at least one email to address j, the graph contains an undirected edge from i to j. The non-Enron email addresses act as sinks and sources in the network as their communication with the Enron email addresses is observed.The graph of routers comprising the Internet can be organized into subgraphs called autonomous systems (AS). Each AS exchanges traffic flows with some neighbors (peers). We can construct a communication network of who-talks-to-whom from the BGP (Border Gateway Protocol) logs. The data was collected from the University of Oregon Route Views Project-Online data and reports [28]. The dataset contains 733 daily instances which span an interval of 785 days from November 8, 1997, to January 2, 2000.Before doing these empirical tests, we had processed the three networks in advance. The largest connected subgraphs of these networks replace their networks, respectively. The p2p-Gnutella06 network and AS network are changed to undirected network in this way that all of one-way edges of network are stored again according to their reverse direction, respectively.In the first empirical test, we randomly select one percent of network nodes as original infected nodes of virus and a node as the original infected node of immune agent. Figure4 displays that the node density infected by the virus interacting with immune agents is smaller than one infected by the virus in pure SIS propagation method and decreases significantly with the increase of effective transmission rate of immunization agents λ2 for different effective transmission rates of virus λ1 in all three networks.The node densityρ(1) infected by virus as a function of virus effective transmission rate λ1, for the different effective transmission rate λ2 of immune agent on different real-world networks, respectively. (a) p2p-Gnutella06 network, (b) Email-Enron network, and (c) AS network. The recovery rate of the virus spread β(1) = 0.25 and the recovery rate of the immune agent spread β(2)=0.5.
(a)
p2p-Gnutella06 network
(b)
Email-Enron network
(c)
As networkIn the second empirical test, we randomly select a node as the virus input source. When the node density infected by virus is more than one percent, immunization agent begins to spread from a randomly selected node and this moment is marked as zero moment, namely,t=0. As shown in Figure 5, the node density infected by the virus interacting with immunization agents first runs high but falls back quickly because of the influence of the immunization agent transmission.The fraction of infected nodes of the virus spread, immunization agent spread, and pure SIS spread as functions of timet, respectively, on different real-world networks. (a) p2p-Gnutella06 network and (b) AS network. Their effective transmission rates are all 0.4. The recovery rate of the virus spread β(1) = 0.25, the recovery rate of the immunization agent spread β(2) = 0.5.
(a)
p2p-Gnutella06 network
(b)
As network


## 5. Conclusion

Threshold analysis of the model is done on BA networks. Immune transmission has a significant impact on the virus spread threshold and the virus infections density in the steady state. The virus propagation threshold can be changed by adjusting the immune effective transmission rate. When the virus effective transmission rate is less than its propagation threshold, the virus is eventually eradicated from the network.In many real situations, the network topology is difficult to obtain globally or the network size is too big to be handled. Dispensing with the analyses of network topological properties, we propose the immune strategy based on the transmission mode. The immune strategy is fast, feasible, and effective. We only need to measure the effective transmission rate of virus and the immune success rate of immune agent for actual implementation of the model, which can be done in the local area of networks. According to the measured parameters, immune effective transmission rate can be set to inhibit the spread of the virus.In realistic setting, many networks are not static. Both its edges and nodes are not continuously active, which has a strong effect on spreading processes. It may be very interesting and significant to analyze the competing dynamics on a complex system with temporal structure. This will also be our future research interest.



---

*Source: 971497-2014-09-01.xml*