Virus on a Network

http://ccl.northwestern.edu/netlogo/models/run.cgi?VirusonaNetwork.752.523

Conclusion

b/g is known, we can learn some formation about largest eigenvalue of the graph.

If number of nodes decreases, percentage of infected nodes increases.

Although b, g are same , percentage of infected nodes changes.

THANKS...

**Models and Algorithms for**

Network Immunization

Network Immunization

Models and Algorithms for

Network Immunization

OVERVIEW

Introduction

Our goal:

Prevent disease spreads,

Minimize epidemic spread

Control the leakage of sensitive information and unpleasant gossip.

Limitations:

Resources; vaccination, anti-virus software, influence

Cost

Solution:

Achieving the best possible effect, while allocating the minimum possible resources.

HOW?

2 different types of models:

The independent-cascade model, considered by Kempe et al. For the propagation of gossip,

Dynamic-propagation model, similar well known SIS model

To Sum Up

A general framework that allows us to formally define the immunization problem.

Two different virus propagation models, and we propose immunization algorithms for these models.

Algorithms experimentally on both real and synthetic networks.

The benefits of our algorithms are especially pronounced in in many real-life networks.

Related Work

Kermack and McKendrick, establishes the first stochastic theory for epidemic spread and proves the existence of an epidemic threshold,

Cohen et al. show that immunizing random acquaintances of random nodes is more effective than immunizing random nodes

Aspnes et al. , assume that nodes in the graph act selfishly and they study inoculation strategies from a gametheoretic point of view.

1.Virus Propagation and

Epidemic Spread

SIR (Susceptible- Infected-Removed) model,

SIS (Susceptible-Infected- Susceptible) model.

1.1 The Independent Cascade Model

A special case of the SIR model.

At time t = 0 the adversary plants r viruses to some nodes of the graph.

S(Nr;G):Expected number of infected nodes

Sr(G) = maxS(Nr;G)

S'r(G) = E [S(Nr;G)]; in case of randomized adv

Problem 1 (EPIDEMIC SPREAD MINIMIZATION):Sr(G')

Problem 2 (EXPECTED EPIDEMIC SPREAD MINIMIZATION):Sr'(G')

1.2.Dynamic Propagation Models

Special cases of the SIS model.

An infected node i propagates the virus to a node j in a single step with propagation probability b, while at the same time an infected node may recover with recovery probability g. The ratio b/g defines the infection rate of the virus.

L(M) be the largest eigenvalue of M.

Condition b/g <1/ L(M) is sufficient for quick recovery of some system.

Theorem 1 Given a graph G with adjacency matrix M,

and infection rate b/g, if b/g <1/L(M) then the expected time until the virus dies out is logarithmic in the number of nodes in the system, against an adaptive adversary.

Theorem 2 Given a graph G with adjacency matrix M,

and infection rate b/g, the expected time until the virus dies

out is logarithmic in the number of nodes in the system if

b/g <1/ L(M), and it is unbounded if b/g >1/ L(M), against an adaptive adversary.

Problem 3 (THRESHOLD MAXIMIZATION) Given a graph

G, and an infection rate b/g, immunize the minimum number of nodes in G, such that b/g<1/L(M'), where M' is

the adjacency matrix of the immunized graph.

2.Immunization Strategies

2.1 The Independent Cascade Model

Minimizing the epidemic spread: Problem 1,

Running time: Greedy Algorithm, O(Q(n^2 + nm)k)

Minimizing the expected epidemic spread: Problem2

Running time:O(Q(n+m)k)

2.2 Dynamic Propagation Models

Epidemic threshold for the dynamic propagation model is equal to the inverse of the largest eigenvalue of the adjacency matrix M.

The objective of the immunization algorithm is to decrease this eigenvalue, while incurring the minimum

possible damage to the network.

Large eigenvalue corresponds to a graph that is densely connected.

Eigenvector values provide information about the global structure of the graph.

EIG performs in general better than the simple MAXDEGREE heuristic that removes the node with the maximum degree, which takes into account only local information

3.Experiments

3.1 Datasets

Scale-free graphs: Barabasi and Albers

Small-world graphs:small characteristic path length and large clustering coefficient.

Co-author graph:8000 authors of papers in VLDB, PODS and SIGMOD at the Collection of Computer Science Bibliographies1

Autonomous Systems (AS) graphs:Autonomous Systems topology of the Internet, 8 such different datasets.

Power-grid graph:Generators,transformers and substations

3.2 The Independent Cascade Model

Introduction

Related Work

Virus Spread

Immunization Strategies

Experiments

Conclusion

New Approach: EIG for epidemic threshold problem, each iteration takes as input a matrix B.

For the first iteration, B = M the system matrix.

Compute the largest eigenvalue L and the corresponding eigenvector w1 of B. Let b/g be the epidemic threshold. If

b/g<L the algorithm stops.

Otherwise, find the node i with the maximum value in the eigenvector w1, and remove it from the graph, that is, remove the corresponding row and column from B.

O(kT)

3.3 The Independent Cascade Model

Our experimental evaluation shows that our algorithms perform better than other heuristics when considering graphs with high clustering coefficient.

Additionally, their performance is not affected

by the average path length of the graph, which makes

our algorithms useful for small-world networks.

Special cases of the SIS model.

An infected node i propagates the virus to a node j in a single step with propagation probability b, while at the same time an infected node may recover with recovery probability g. The ratio b/g defines the infection rate of the virus.

L(M) be the largest eigenvalue of M.

Condition b/g <1/ L(M) is sufficient for quick recovery of the system.

c=0.64 c=0.42

q=probability ,an edge from the initial lattice is rewired to connect to another node