CLUSTERING COEFFICIENT

Duncan J. Watts and Steven Strogatz (1998) introduced the 'clustering coefficient'^[1] 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\_1,v\_2,dots,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:
: $N\_i\; =\; \{v\_j\}\; :\; e\_\{ij\}\; in\; E.$
The degree $k\_i$ of a vertex is the number of vertices, $|N\_i|$, 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 ($k\_i$ is the total (in + out) degree of the vertex). Thus, the 'clustering coefficient for directed graphs' is given as
:
An undirected graph has the property that $e\_\{ij\}$ and $e\_\{ji\}$ are considered identical. Therefore, if a vertex $v\_i$ has $k\_i$ neighbours, edges could exist among the vertices within the neighbourhood. Thus, the 'clustering coefficient for undirected graphs' can be defined as
:
Let $lambda\_G(v)$ be the number of triangles on $v\; in\; V(G)$ for undirected graph $G$. That is, $lambda\_G(v)$ is the number of subgraphs of $G$ with 3 edges and 3 vertices, one of which is $v$. Let $au\_G(v)$ be the number of triples on $v\; in\; G$. That is, $au\_G(v)$ is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is $v$ and such that $v$ is incident to both edges. Then we can also define the clustering coefficient as
:
It is simple to show that the two preceding definitions are the same, since
:
These measures are 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:
:
A graph is considered small-world, if its average clustering coefficient is significantly higher than a random graph constructed on the same vertex set.

Contents

References

References

1. Watts, D. J. and Strogatz, S. H. "Collective dynamics of 'small-world' networks." http://tam.cornell.edu/SS_nature_smallworld.pdf