Assignment Project: Simulating Covid 19
To do this project, we need to learn some prerequisites first :-)
Priority Queues:
This project involves you to do some "extracurricular" reading about priority queues. A priority queue is like a regular queue that we discussed in the class, except that there is a "priority" associated with each element. There is also a notion of serving the elements in the queue, with higher priority elements being served first. There are several ways of implementing this ADT-I will not worry about how you implement it. A naive implementation using linked lists is also fine. Often, a data structure called the heap is used. I strongly urge you to read this as well.
In particular, and relevant to us, priority queues are useful in implementing "discrete event simulations";
We will use this application of the priority queue to study the epidemic.
Graphs and Adjacency Matrices
The next thing that you would need to learn to do this project is a very basic idea of graphs or networks. A network is a collection of nodes or vertices, which are connected by edges. Therefore, if we want to model individuals in a population and their contacts, one way to do is to model a person using a node and if two persons are in close contact with each other, we will model that by placing an edge between them. If they are not, then there is no edge between them. Obviously, if two nodes are connected by an edge, they are said to be adjacent to each other. Such a structure of nodes and edges is called an (undirected) graph. Never mind about the undirected part for this project. One way of representing a graph in a computer is using an adjacency matrix. This can be implementing using linked lists.
Some Computational Epidemiology
An epidemic like Covid-19 is an SIR epidemic. An individual is initially Susceptible (S). Then s/he might get Infected (I) and finally Recover (R). However, as one can expect, each transition is probabilistic.
You have to implement a simple variant of the algorithm in section of A.1.2 of:
And obtain the infection curves1.
Reproduced here is a part of the algorithm, with some modifications.
Algorithm 1 Part of Fast SIR
while Q is not empty do do
Event earliest remaining event in Q
if Event.action is transmit then
if Event.node.status is susceptible then
process trans SIR(G, Event.node, τ , γ) [See Below]
else Event is Recovery
process rec SIR(Event.node, Event.time) [See Below]
end if
end if end while
An event struct in the priority queue has to necessarily have the following fields- a) the time when the event occurs, b) the type of event (transmit or re- cover) and c) which node it concerns. Other fields are as per your programming convenience. Also, maintain lists of S, I and R people.
process trans SIR
If the event is a transmit event and the corresponding node v is susceptible, delete v from the S list and add it to the I list. Create events for The source code is available in python in this document. You are encouraged to read that code (learn python in the process if you haven't already.
With the time at which this happens. You can use the following subroutine to determine these times. For each neighbor, toss a coin with The node v transmitting the infection to its neighbors, along probability τ for each day until you get a heads. For the day you get a heads, put a transmit event for that neighbor. (Think how you can (biased) toss coins in C).
v's recovery. Toss a biased coin with γ probability of it showing heads. Keep tossing until you get a heads. If you get a heads on the ith trial, v will recover after i days. (So, we create an event for that and insert in the priority queue.)
process rec SIR
If the event is a recover event, then remove that node from the I list and add it to the R list.
So what do we have to do?
Perform this simulation for a maximum of 300 days, use τ as 0.5 and γ as 0.2. Construct a graph of 10000 nodes with MAX VERTICES as 10000 and MAX EDGES as 3000
Attachment:- Simulating Covid 19.rar