Consider an undirected graph G=(V,E) representing a population. Nodes of the graph are individuals. The presence of an edge between two individuals indicates that they are in close contact with each other (e.g, sharing a home or a workplace).
Generate a graph on 100 nodes as follows: for each pair of nodes, toss a fair coin and put an edge between them if and only if you get a heads. This gives you a population graph. Every individual is in one of the following states: susceptible, infected, or recovered (aka removed). The possible transition for each individual is susceptible to infected to recovered.
● Data Structures:
○ Sets S, I and R.
○ Binary heap with nodes having
■ Node id
■ TimeStamp
■ Event type: Infection/Recovery ● Initially all nodes are in S.
● Choose a starting node arbitrarily and call it u.
● Insert this infection event in the min-Queue Q, with timestamp 0. ● While(;;)
○ e<-DeleteMin(Q)
○ If e is a Recovery event,
■ R<- R U {e.nodeID}
■ I<- I{e.nodeID}
○ If e is an infection event,
■ I<- I U {e.nodeID}
■ S<- S{e.nodeID}
■ Forall susceptible neighbors u of e.nodeId
● Generate an infectionTime as follows
○ Toss a fair coin five times
○ Let j be the first time a head comes (if a head doesn’t appear at all, u doesn’t get infected because of e.nodeid), continue to next neighbor ● Insert into Q:
○ Node id:u
○ TimeStamp: e.timeStamp+j
○ Event type: Infection
● (If u did get infected) generate recovery event:
○ Generate a random number k uniformly between
e.timeStamp+j and e.timeStamp+j+5 ● Insert into Q:
○ Node id:u
○ TimeStamp: k
○ Event type: Recovery
1. Plot the number of susceptible, infected and recovered individuals, against i.
2. Compare the instant at which a node gets infected with it’s shortest distance from the start node s.
