Monday, April 9, 2012

Immunization and Epidemic Dynamics in Complex Networks

The study of epidemic spreading is based upon the notion that a disease is conveyed by contact between an infected individual and an uninfected individual who is susceptible to the disease. An endemic stage is reached if a finite fraction of the population is infected. Similarly, this notion may describe the spreading of a computer virus through a network of computers. Recently, it has been shown that in a class of scale free networks an epidemic may spread regardless of how low is its rate of infection. Further discussion is done on static and sparse networks.


The SIR model represents the development of a disease in a network of connected individuals. S stands for the susceptible stage, where the individual is healthy. I stands for the infected stage, where the individual is infected with the disease and can infect other individuals in contact with it. R is the removed stage, where the individual is either recovered and has acquired immunization to the disease or otherwise permanently removed from the system.

One of the nicest features of the SIR model is that despite it being a dynamic model it can be mapped into a completely static one. Consider a network where each node transmits the epidemic to each of its neighbors with rate r, and is removed with average recovery time τ.The infection can be, therefore, considered as a Poisson process, with average rτ. Thus, the probability for each neighbor not to be infected is e−rτ.

A site can be reached by one of its k links, its probability of being reached is kP(k) / (N<k>)  where N is the number of nodes, P(k) is the fraction of nodes having degree  k, and <k> =  Σ kkP(k) denotes the average degree of nodes in the network.

Since the network is randomly connected, as long as the epidemic is not spread yet, the average number of influenced neighbors is:



General immunization can be seen as a site percolation problem. Each immunized individual can be regarded as a site which is removed from the network. The goal of the immunization process is to pass (or at least approach) the percolation threshold, leading to minimization of the number of infected individuals. The complete model of SIR and immunization can be considered as a site–bond percolation model, and the immunization is considered successful if the network is below the percolation threshold.

Random Immunization:
Studies of percolation on broad-scale networks show that a large fraction fc of the nodes need to be removed (immunized) before the integrity of the network is compromised. In particular it is true for scale free networks.With a random immunization strategy almost all of the nodes need to be immunized before an epidemic is arrested (see Fig. 1).
is the immunization threshold where ps = 1-f  . The probability of each of its k − 1 outgoing links of infecting its neighbor is pb. 

Targeted Immunization:

When the most highly connected nodes are targeted first, removal of just a small fraction of the nodes results in the network’s disintegration. This has led to the suggestion of targeted immunization of the HUBs (the most highly connected nodes in the network). The simplest targeted immunization strategy calls for the immunization of the most highly connected individuals. To use this approach, the number of connections of each individual should be known (at least approximately). In this case, the probability that a site is not immunized, when the immunization rate is f, is θf (k), where,
 and k* and 0 < c <=1 are determined by the condition 

is the critical immunization threshold.

Fig:1 Critical immunization threshold fc as a function of γ in scale free networks(with m=1) for the random immunisation(♦) and targeted immunization ( [] ) strategies. Curves represent analytical results while data points represent simulation data.Full symbols are for random and acquaintance immunization of assortatively mixed networks.

Fig. 2. Critical concentration, fc, for the bimodal distribution (of two Gaussians) as a function of d, the distance between the modes. The first Gaussian is centered at k = 3 and the second one at k = d + 3 with height 5% of the first. Both have variance 2 (solid lines) or 8 (dashed lines). Top 2 lines are for random immunization. The bottom 2 lines are for acquaintance immunization. Note that also for the case d = 0, i.e. a single Gaussian, the value of fc reduces considerably due to the acquaintance immunization strategy. Thus the strategy gives improved performance even for relatively narrow distributions.

Fig. 3. Critical concentration, fc, vs. r, the infection rate, for the SIR model with τ = 1. The solid lines are for random (top) and acquaintance immunization (bottom) for scale-free networks with γ = 2.5. The dashed lines are for γ = 3.5 (top – random, bottom – acquaintance immunization). The circles represent simulation results for acquaintance immunization for scale-free networks with γ = 2.5.

Fraction of endemic outbreaks pe , as a fuction of the fraction of immunized individuals f, for random immunization,acquaintance immunization, and targeted immunization strategies.

Practical  Issues:

Various immunization strategies have been proposed, mainly for the case of an already spread disease, and are based on tracing the chain of infection towards the superspreaders of the disease. This approach is different from our proposed approach, since it is mainly aimed at stopping an epidemic after the outbreak began. It is also applicable for cases where no immunization exists and only treatment for already infected individuals is possible. Our approach, on the other hand, can be used even before the epidemic starts spreading, since it does not require any knowledge of the chain of infection. In practice, any population immunization strategy must take into account issues of attempted manipulation. We would expect the suggested strategy to be less sensitive to manipulations than targeted immunization strategies. This is due to its dependence on acquaintance reports, rather than on self-estimates of number of contacts. Since a node’s reported contacts pose a direct threat to the node (and relations), we anticipate that manipulations would be less frequent. Furthermore, we would suggest adding some randomness to the process: for example, reported acquaintances are not immunized, with some small probability (smaller than the random epidemic threshold), while randomly selected individuals are immunized directly, with some low probability. This will have a small impact on the efficiency, while enhancing privacy and rendering manipulations less practical.

No comments:

Post a Comment