|
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 <math>n<math> vertices <math>V={v_1,v_2,...v_n}<math> and a set of edges <math>E<math>, where <math>e_{ij}<math> denotes an edge between vertices <math>v_i<math> and <math>v_j<math>. Below we assume <math>v_i<math>, <math>v_j<math> and <math>v_k<math> are members of V.
We define the neighbourhood N for a vertex <math>v_i<math> as its immediately connected neighbours as follows:
<math>N_i = \{v_j\} : e_{ij} \in E<math>
The degree <math>k_i<math> of vertex is the number of vertices in its neighbourhood <math>|N_i|<math>.
The clustering coefficient <math>C_i<math> for a vertex <math>v_i<math> is the proportion of links between the vertices within its neighbourhood divided by the number of links that could possibily exist between them. For a directed graph, <math>e_{ij}<math> is distinct from <math>e_{ji}<math>, and therefore for each neighbourhood <math>N_i<math> there are <math>2k_i(k_i-1)<math> links that could exist among the vertices within the neighbourhood. Thus, the clustering coefficient is given as:
<math>C_i = \frac{|\{e_{jk}\}|}{2k_i(k_i-1)} : v_j,v_k \in N_i, e_{jk} \in E<math>
This measure is 1 if every neighbour connected to <math>v_i<math> is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to <math>v_i<math> connects to any other vertex that is connected to <math>v_i<math>.
The clustering coefficient for the whole system is given by Watts and Strogatz as the average of the clustering coefficient for each vertex:
<math>\overline{C} = \sum_{i=1}^{n} \frac{C_i}{n}<math>
References
- Watts, D. J. and Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature 393, 440--442 (4 June 1998).
| 
