Clustering Coefficient - Local Clustering Coefficient

The local clustering coefficient of a vertex (node) in a graph quantifies how close its neighbors are to being a clique (complete graph). Duncan J. Watts and Steven Strogatz introduced the measure in 1998 to determine whether a graph is a small-world network.

A graph formally consists of a set of vertices and a set of edges between them. An edge connects vertex with vertex .

The neighbourhood for a vertex is defined as its immediately connected neighbours as follows:

We define as the number of vertices, in the neighbourhood, of a vertex.

The local clustering coefficient for a vertex is then given by 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, is distinct from, and therefore for each neighbourhood there are links that could exist among the vertices within the neighbourhood ( is the number of neighbors of a vertex). Thus, the local clustering coefficient for directed graphs is given as

An undirected graph has the property that and are considered identical. Therefore, if a vertex has neighbours, edges could exist among the vertices within the neighbourhood. Thus, the local clustering coefficient for undirected graphs can be defined as

Let be the number of triangles on for undirected graph . That is, is the number of subgraphs of with 3 edges and 3 vertices, one of which is . Let be the number of triples on . That is, is the number of subgraphs (not necessarily induced) with 2 edges and 3 vertices, one of which is and such that 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 is also connected to every other vertex within the neighbourhood, and 0 if no vertex that is connected to connects to any other vertex that is connected to .