Simulations on Small World Graphs

Up to now, it is not easy to give a well-defined property that ditinguishes "small world" graphs from other graphs. But good news is that we have techniques to tell whether the "small world" phenomenon is happening on a given graph. In general, if a graph is very cliquish but average distance between vertices are small, then this graph is "small world". By the seminal paper by Watts & Strogatz, we can quantify cliquishness and average distance.

What is the idea of doing simulations on small world graph? Well, we can do certain simulation on a "small world" graph and also on "non-small-world" graph with similar structure. If the results on different graphs are significantly different, then we know this simulation process captures certain property of "small world" graph.

Disease spreading simulation by Watts & Strogatz.
This simulation is one that reveals a property of "small world" graph.

Simulation Process	At time 0, an infective vertex is introduced, other vertices are healthy. At each time unit, an infective vertex can infect each of its healthy neighbors with probability r. But after a time unit, an infected vertex stops infecting(by immunity or death).
Graph to run simulation	A regular ring latice is the "non-small-world" graph. We start from a regular ring, and make the each incident edge of each vertex randomly rewired with probility p. In this way, we have a "small-world" graph if we give a small value to p which is close to 0. [Watts & Strogatz]
Result	Let R be the infectiousness probability needed to get half of the population infected. R decreases rapidly with small p.

Same simulation by me on a different "small-world" graph model.
Graph model:
We start from a n by n 2-D grid. It is not a "small-world" graph since the average edge distance is da=2/3*n. It is believed that da should be in order of log n.
Then we make it "small world", each vertex can be added an extra edge with probility p, and the other end vertex of the extra edge is randomly selected.

2-D grid	Randomly rewired 2-D grid

Result:
We run the simulation on a 100 by 100 grid. And we use a 200 by 200 image to represent the simulation result. That is, a vertex in the grid is represented by a 2 by 2 spot in the image, infected vertices are drawn black. Then we have a visual tool to see how the disease is spreading. BTW, the fisrt infected vertex is always at the center of the grid.

Or if your browser does not run the applet, here is the java application vertion.