From ScribbleWiki: Analysis of Social Media

Epidemic Spreading in Real Networks: An Eigenvalue Viewpoint

• Authors: Wang Y., Chakrabarti D., Wang C. and Faloutsos C.
• Conference: 22nd Symposium on Reliable Distributed Computing, Florence, Italy, Oct. 6-8, 2003.
• Link: http://www-2.cs.cmu.edu/afs/cs.cmu.edu/user/christos/www/PUBLICATIONS/srds03-virus.pdf
• Maintainer: Sameer Badaskar

Introduction

It is often of interest to know whether the attack of a virus on a network results in an epidemic. Here, epidemic means a large percentage of nodes of the nodes of a network getting infected. Epidemological models find use in practical situations like:

1. Analyzing spread of viruses in a computer network, an epidemic can result in a network shutdown.
2. Spreading of a piece of information (eg: rumor) among a network of connected individuals.
3. The effectiveness of a word-of-mouth marketing campaign by a product retailer.

The conditions for a viral epidemic to occur depend on three parameters and most epidemological models use these for analysis

1. Virus birth rate or infect rate <math>\beta</math>
2. Death rate or cure rate of the virus <math>\delta</math>
3. Topology of the network (represented by an adjacency matrix <math>A = [a_{ij}]</math>)

The main contribution of this paper is to arrive at a condition for an epidemic to occur (epidemic threshold)in a network. Specifically, the epidemic threshold is related to the principal eigenvalue of the network adjacency matrix. This condition can apply for any kind of network irrespective of its topology. It is also proved both theoretically and in simulations that if the epidemic threshold falls below the critical value, the number of infected nodes tend to zero in the steady state.

Other Epidemological Models

Most analysis of network epidemics has focused on a particular family of networks. For example, in the case of homogeneous networks, every node is supposed to be connected equally to the others. In such a case an epidemic occurs if the epidemic threshold (ratio of birth-rate to death-rate of a virus) exceeds the reciprocal of the average connectivity of nodes of the network. However, this analysis does not hold good for non-homogeneous networks like power law networks which are more practical examples of real world networks. Other epidemic analyses have concentrated on specific forms of power law networks. The SV model for a specific power law network equates the epidemic threshold to the ratio of average connectivity of the network to the expected divergence of the network connectivity. This paper derives the value for epidemic threshold that does not assume any particular network topology.

Proposed Epidemic Model

Let <math>p_t</math> be a column-vector of N rows where the i-th row represents the probability of the i-th node getting infected at time t <math>p_{i,t}</math>. It is shown with some approximation that

• <math> p_t = ((1 - \delta) I + \beta A) p_{t-1} </math>
• <math> p_t = B p_{t-1} </math>
• <math> B = ((1 - \delta) I + \beta A)</math>

where

• I is the identity matrix
• A is the adjacency matrix of the network

An epidemic is said to occur if <math> \sum_i p_{i,t} = N </math> as t tends to infinity (in the steady state). We see that

• <math> p_t = B^t p_0 </math>

Eigen analysis of the matrix B shows that

• <math> p_t \approx e^t p_0 </math> where e is the principal eigenvalue of

the matrix B. If e < 1, p_t tends to 0 as t tends to infinity (steady state) and no epidemic happens

• e < 1 implies that for an epidemic to 'not happen, the ratio of birth-rate to death-rate of a virus

should be less that the reciprocal of the principal eigenvalue of the network adjacency matrix.

Thus the epidemic threshold is equal to reciprocal of the principal eigenvalue of the network adjacency matrix. If e < 1, the number of infected nodes in the network decrease exponentially in time. This analysis confirms for special cases like

1. Homogeneous graphs where the principal eigenvalue is the average connectivity in which case the epidemic threshold is reciprocal of average connectivity as in the previous section.
2. For a Star-topology, the principal eigenvalue is given by the square-root of the outdegree

of the central node.

Physical Interpretation

Since the epidemic threshold is related to the principal eigenvalue, it is also connected with the principal eigenvector of the matrix. The principal eigenvector represents the most well connected nodes of the network. What this implies is that for an epidemic to happen, the most well connected nodes of the network need to be infected. This interpretation is quite intuitive especially in the case of biological viruses. Well connected can mean the most trusted nodes or nodes that are connected to many well connected nodes.

Experiments

Simulations were performed on different topologies like star, power-law and an actual network itself. The graphs of the number of infected nodes vs. time show that the predictions of the proposed epidemic model are more closer to simulations than the homogeneous model or the SV model.

Critique

Though this paper derives a condition for an epidemic to happen irrespective of the nature of the network topology, few questions remain unanswered:

1. More clarity on the experimental comparison is required. Especially the manner in which the benchmark simulations were performed.
2. How the model behaves with a temporally changing structure (links made/broken, new nodes added) of the network. If the eigen-gap between the first and the second largest eigenvalues is large, the epidemic threshold will remain the same. Else, it would get change to reciprocal of the second largest eigen-value.
3. It makes intuitive sense to infect the most connected nodes for an epidemic to occur. However, it has been shown in the case of networks like product-recommendation network and email-information spreading networks that this intuition is not correct. This means that the notion of connection between any two nodes needs to be defined better rather than just a link between them.