Describing a Small World Graph

Main Menu Previous Topic Next Topic

**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 k_{i}
immediate neighbors, then we can define the Clustering Coefficient for
agent i, C_{i}, as the fraction of the total possible
k_{i}*(k_{i}-1) / 2 connections that
are realized between i's neighbors (2). The Clustering Coefficient
for the society, C, is just
the average of the C_{i}'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.

^{1}Close 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.

^{2}If a given agent i has no neighbors or just one neighbor, we define C_{i}=1.

Previous Slide Next Slide