Math Insight

Clustering coefficient definition

 

The clustering coefficient1 of an undirected graph is a measure of the number of triangles in a graph.

The clustering coefficient of a graph is based on a local clustering coefficient for each node \begin{gather*} C_i = \frac{\text{number of triangles connected to node $i$}}{\text{number of triples centered around node $i$}}, \end{gather*} where a triple centered around node $i$ is a set of two edges connected to node $i$. (If the degree of node $i$ is 0 or 1, we which gives us $C_i=0/0$, we can set $C_i=0$.)

The clustering coefficient for the whole graph is the average of the local values $C_i$ \begin{gather*} C= \frac{1}{n}\sum_{i=1}^n C_i, \end{gather*} where $n$ is the number of nodes in the network.

By definition $0 \le C_i \le 1$ and $0 \le C \le 1$.

The clustering coefficient of a graph is closely related to the transitivity of a graph, as both measure the relative frequency of triangles.