Describing a Small World Graph

Formal Measures

In order to examine this problem more closely, we will require a more precise definition of a Small World society. To this end, we will begin by defining two key measures: Characteristic Path Length and Clustering Coefficient (1).

Characteristic Path Length (L) is simply defined as the average distance between any two agents, or more precisely, the average length of the shortest path connecting each pair of agents. All edges are unweighted and undirected, so the distance between agents is simply the minimal number of edges that must be traversed to get from one agent to the other. L is generally a measure of the global properties of a graph and, as we will see, can be quite independent of local structure.

Characteristic Path Length is only a meaningful measure if a graph is fully connected -- i.e. if there is a sequence of edges joining any two agents. We adopt the convention that L is infinite if a graph is not connected. In general, to make comparisons more feasible, all graphs we deal with will be fully connected.

Clustering Coefficient (C) is a measure of how clustered, or locally structured, a graph is. The Clustering Coefficient is an average of how interconnected each agent's neighbors are. Specifically, if agent i has ki immediate neighbors, then we can define the Clustering Coefficient for agent i, Ci, as the fraction of the total possible ki*(ki-1) / 2 connections that are realized between i's neighbors (2). The Clustering Coefficient for the society, C, is just the average of the Ci's. Loosely speaking, the Clustering Coefficient measures how close each agent's neighborhood is to a clique.

If a graph is fully connected, then it is easy to see that C equals 1, its maximum value. However, a more interesting case occurs if the graph is sparse -- that is if the number of links in a graph is small compared to the total number of possible links. On the next slide, we will see that even in a sparse graph, C can remain high.

1Close readers will note that the measures as we define them are subtly different from Watt's original measures. As we will see, these differences will not affect our results.

2If a given agent i has no neighbors or just one neighbor, we define Ci=1.

Previous Slide                                                           Next Slide