Describing a Small World Graph

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

To the left is a graph Watts denotes a connected caveman graph. Each set of agents is in a small interconnected "cave" or cluster, and the last agent in each cluster is connected to the first agent of the next cluster. This type of graph has a high clustering coefficient and a high path length.

We let k represent the average number of connections an agent has. As before, N represents the total number of agents. Thus, the total number of connections in the graph is k x N / 2. The caveman graph is sparse in the sense that k is much smaller than N. The graph consists of N/(k+1) clusters. Within each cluster, each agent knows every other agent. Thus, the clustering coefficient is within a small fraction of the maximum possible clustering coefficient of a connected sparse graph, and very close to 1.

The characteristic path length of a connected caveman graph is on the order of N/k. Hence, as N gets large and the graph remains sparse, L grows steadily.

The caveman graph thus represents one type of extreme graph -- high clustering coefficient and large characteristic path length .

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