Creating a Small World Graph

A Recipe for a Small World Graph

Note: in order to run the simulation referred to in this slide, go here, to the Java Applet version. You will be directed to download the latest version of the Java plug-in.

In trying to create a small world graph, we might try to mimic the way that social connections are formed. For instance, there is always some small probability that a given person will meet any other random person on the planet. However, that probability immediately increases if the two people share a common acquaintance. The more acquaintances the people share, the more likely they are to meet.

How can we model this mathematically? Suppose that agents i and j share mi,j mutual acquaintances. We require that the probability that agent i meets agent j depends only on mi,j. Watts adopts the following function to describe this process:

where p is some small base probability level. The Ri,j values must be normalized to one to create a probability distribution. That is, the probability that agent i chooses to connect to agent j is proportional to Ri,j. We choose agents in a random order and allow them to select a partner by this process until we have created the correct number of connections.

The parameter alpha captures the rate at which mutual acquaintances affect the probability of interaction. Our alpha is actually a factor of 100 times larger than the parameter originally employed by Watts, but this will not affect our results. For large alpha, the probability of meeting remains low until agents share at least k acquaintances. This corresponds most closely to the near-random Solaris graph. For small alpha, the probability of meeting immediately jumps to a high value with one mutual contact and then remains there regardless of how many more mutual contacts appear. This corresponds most closely to the clustered caveman graph

A problem with this method of constructing a society is that disconnected graphs often result. Because of this, we actually use a compromise method in which we first create a topological ring of agents to ensure that the graph is connected and then proceed according to the above algorithm.

The graph below is provided for demonstration. You can enter a value for alpha, and then press "Go" to connect the society according to the Watts algorithm. Try setting alpha to 1 or to 20000, and note the difference in the graph.

The graph below has N=100 agents. When "Go" is pressed, it is connected with k=6.