Describing a Small World Graph

Main Menu Previous Topic Next Topic

**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