Describing a Small World Graph

Random 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.

We saw that the caveman graph is a highly clustered graph with a high path length. On the opposite extreme, a randomly connected graph typically has a low clustering coefficient and low path length. Although a randomly connected graph does not exhibit absolute minimal path length for arbitrary N and k, it is a good approximation.

Path Length for a random graph grows proportionally to just log(N) / log(k), unlike the N/k for a caveman graph. Thus, with very large N, the discrepancy between L for a random graph and L for a caveman graph can become quite extreme. Also, for a random graph, C remains low -- on the order of k/N ( recall that C for a caveman graph is close to 1.) Hence, it is fair to say that a random graph is in some sense opposite to the caveman graph -- it is another type of extreme graph, with low clustering and low path length .

To be fully precise, the graph on the left is not a true random graph. Rather, it is what Watts calls a Solaris graph. This graph was created by first connecting all the agents in a ring, and then allowing agents (in a random order) to choose random partners until the number of connections per agent is k. Thus, a Solaris graph has very similar properties to a randomly connected graph. Note that by connecting the agents in a ring first, we ensure that the entire graph is connected.

The graph to the left was created with the values: k=6 and N=42.

Previous Slide                                                           Next Slide