Watts and Strogatz (1998) introduce the clustering coefficient graph measure to determine whether or not a graph is a small-world network.

First, let us define a graph in terms of a set of n vertices V = v₁,v₂,...v_n and a set of edges E, where e_ij denotes an edge between vertices v_i and v_j. Below we assume v_i, v_j and v_k are members of V.

We define the neighbourhood N for a vertex v_i as its immediately connected neighbours as follows:

The degree k_i of vertex is the number of vertices in its neighbourhood | N_i | .

The clustering coefficient C_i for a vertex v_i is the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibly exist between them. For a directed graph, e_ij is distinct from e_ji, and therefore for each neighbourhood N_i there are k_i(k_i - 1) links that could exist among the vertices within the neighbourhood. Thus, the clustering coefficient is given as:

This measure is 1 if every neighbour connected to v_i is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to v_i connects to any other vertex that is connected to v_i.

The clustering coefficient for the whole system is given by Watts and Strogatz as the average of the clustering coefficient for each vertex:

References

• Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature 393, 440--442 (4 June 1998).