Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Models and Algorithms for Network Immunization

No description
by

epidemic r

on 17 August 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Models and Algorithms for Network Immunization

Conclusion
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

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
Full transcript