Week 4 & 5

This post will be a two in one since I forgot to write a post last week. So we're about half way through the program and I've certainly learned a lot. The past couple of weeks we spent looking into ways to simulate disease spread on our graphs. I made a nice basic simulator to model diseases. We've also made plans of how to further explore this subject as is pertains to our large graphs.

Disease Simulator

The big achievement I've made this week is creating our mini simulator so that we may begin studying how a disease will spread in these graphs. The simulator implements a basic SIR model. The SIR model stands for Susceptible, Infectious, and Recovered. Each of these represents a state that an agent can be in. When an agent is susceptible, they are healthy uninfected individuals. When a susceptible agent comes in contact with an infectious agent, there is a chance the agent will transition to the infectious state themselves. In the infectious state, an agent may infect other susceptible agents until their infectious period elapses. The infectious period is a pre-defined amount of time that an agent will remain infectious. At the end of this period, the agent will transition to the recovered state. In this state, they will no longer infect other agents, and they themselves can never be infected again. This state diagram can be represented as the following:

[ Susceptible ] -> [ Infectious ] -> [ Recovered ]

There are variations of this model where agents can be reinfected. Also we can add cases where an agent is a carrier, as in they carry the disease and infect others, but do not show symptoms. This is also represented by different infectious periods. We could also introduce vaccines, where some agents are much more immune to the infection and are therefore less likely to become infected. This simulation I have built only deals with the simple SIR model. However it can be expanded in the future without much issue.

The simulation runs in the following manner:

• All agents start as susceptible
• One agent is randomly selected as patient zero and becomes infectious
• Loop for the duration of the simulation:
  • For each infected agent:
    • Try to infect each neighbor
    • If infectious period has elapsed, set state to recovered.

When the simulation is run, the user is asked to input some parameters for the experiment. The first is the infectious probability. This is a number between 0 and 1 that determines how likely an individual is to be infected. The next parameter is how long to run the simulation. This is an arbitrary time unit that you can imagine as days, weeks, months or whatever. The last parameter is the infectious period. Again this is how many time steps an agent will remain in the infectious state.

The program will take these parameters and run the simulation using the steps above. When it is done, it will dump the results into a file which we can use to display some nice charts in the web browser.

Now as nice as it would be to display the infection in real time visually, this is extremely difficult due to the complexity of these large graphs. Perhaps in the future I can display some very rudimentary visualization technique.

Results

So now that we have this simulation, we can run it on some of our graphs and begin to make assumptions about the data. Let's take a look at one I ran:

For this experiment, I chose a graph that was fairly evenly distributed. If you recall my last post, that means that most nodes had a good distribution of how many neighbors each had. I gave the infection a chance of 15% to infect another agent, set the duration for 500 time steps, and the infectious period for 8 timesteps. The chart on the left shows how many new infections appeared at each time step. This averaged around 450-500 infections per time step. The graph on the right shows how the population changed over time. If you look at the stats in the box, you can see that about 99.94% of the population was infected with the disease before everyone recovered. Remember this simulation is run without the assumption of any preventative measures. So think of it as no one washes their hands, and people are way too comfortable with each other.

So with this in mind, let's take a look at an example where agents are less connected. We can think of this as a case where people are more distant and don't connect with as many people on a day to day basis. However, still nobody washes their hands. (when will they learn?)

As we can see, this graph paints a bit of a different picture. Due to the nature of this graph I had to alter the parameters a bit to get some good data. Using the old parameters didn't change the outcome much. As we can see from this picture, we were only able to infect 83.13% of the population. The left chart shows us that by time step 12, we weren't infecting any new agents. However if you look at the right chart, you can clearly see people were still infectious at that time. From that data, we can make the assumption that the infectious individuals were not connected to any susceptible individuals.

Next Steps

Now that we have this small simulation, we want to begin looking at something called clusters in the graphs. This is where a group of nodes is more tightly connected with each other than other nodes. However these clusters (or communities) are also connected to each other usually by one or more nodes. As a real world example, think of it this way: I have a group of friends I hang out with at school. But I also have a group of friends I hang out with outside of school. I'm friends with all of these people in both groups, but my school friends are not friends with my non-school friends. What we would like to see is what happens when say one of my school friends gets sick and spreads it to our community and observe say how I could get sick then spread that infection to my non-school community. This can give us an idea of how these communities aid in the spread of disease throughout the greater area.

Week 3

Week 3 is done. And I think I've learned a lot this week. Probably everything I ever wanted to know about big graphs. But there's still more to learn in that area. This week was mainly spent analyzing large graph files given to me by Dr. Mikler. There was a lot of data to look through and it definitely gave me a better insight as to how this data can be processed and utilized. So let's take a look at what we did.

Analyzing Large Graphs

Dr. Mikler comes in and dumps these large files on us that contain HUGE graphs. So the first thing we need to do is figure out a way to read these files. Each file had thousands of lines of node pairs. They corresponded to the edges of the graph in the following format:

sourceNode destinationNode weight

This made it rather simple to write a program to read in the data. I made a small data structure that would essentially build an adjacency list in memory. An adjacency list is a way of representing a graph by first declaring a node followed by each node connected to that node. For instance the following adjacency list:

1 2 3
2 1 4
3 1
4 2

Would represent this graph:

Now think of this on the scale of thousands of nodes. Reading this data into the program from the file takes the longest by far. This is due to I/O constraints from the OS we're running on. We could parallelize this part, but that gets complicated due to calculating positions in the file. Once we get this data into the data structure, we can do all kinds of things with it to calculate different statistics. And thanks to parallelization, we can drastically cut down the time this takes.

The first piece of data we get is the number of nodes in the graph. This is valuable because with this number, we can split up the work equally amongst our threads to perform other calculations. Most importantly, we can start looking into statistics relating to the degree of the nodes. The degree is the number of connected, or adjacent nodes to a given node. For example, if a node has 3 nodes adjacent to it, it is said to have a degree of 3. This data can tell us how dense a graph is. The more dense, the shorter the distance you are likely to travel from one node to another that is more than one node away. By sorting through our graph data structure, we can see the highest degree a node might have, the lowest degree, and the average degree. This paints part of the picture of how these graphs may look.

Visualizing this distribution

Nothing tells you information like a picture. Or more specifically a graph (This time I mean a line graph. Let's call it a chart). Printing out the numbers from the program discussed above gave us some information. But we'd really like to see the whole picture of the degree distribution. This helps us see how dense the graph really is, as well as a better idea of how many nodes are connected. I had the program count the degrees of each node and store how many nodes had a certain degree. This data was dumped into another file. I wrote a quick web page which would display the data on a line chart so we could see the distribution of degrees. Ideally we'd like to see a bell curve on this chart to indicate an equal distribution. Some graphs had that:

Other graphs were slightly less uniform:

On the x axis you can see the "degree", how many nodes connected to a given node. On the y axis is the number of nodes in the analyzed graph that have that given degree. In the first example, the most common degree in the graph was 10. 12,180 nodes shared that degree. Which means there were 12,180 nodes that were each connected to 10 other nodes. In the second example, while not as uniform in distribution, the graph shows to be more dense. We can see the most common degree is 88, which is significantly higher than the previous graph. This is likely due to the larger number of edges. The second graph contains 3.3 million edges compared to 500,000 in the first graph.

Using this tool we can get an idea of the overall density of these large graphs. This will help us to craft solutions for processing these graphs for whatever purpose we may have. One way is using these graphs to represent a network of agents and observing how an infection could spread through these graphs. My hypothesis is with high densities like these, it will travel very fast through the network.