Definition

In graph theory, a clustering coefficient is a measure of the degree to which nodes in a graph tend to cluster together.

Evidence suggests that in most real-world networks, and in particular social networks, nodes tend to create tightly knit groups characterised by a relatively high density of connections; this likelihood tends to be greater than the average probability. of a tie randomly established between two nodes.

Types of Clustering Coefficients

There are two types of Clustering Coefficients:

Global Clustering Coefficient

Local Clustering Coefficient

Average Clustering Coefficient

Global Clustering Coefficient

The Global Clustering Coefficient is based on triplets of nodes:
A triplet is defined as an undirected three nodes connected by: either two (open triplet) or three (closed triplet)

∴ A triangle graph includes:

three closed triplets, one centered on each of the nodes. -- the three triplets in a triangle is dervied from overlapping selections of nodes. This measure gives an indication of the clustering in the entire network (global) It is also applicable to directed networks or transitivity

                   _{number of closed triplets}
C = ^{__________________________________________
            total number of triplets (open & closed)}


The number of closed triplets also referred to as 3 × triangles △ .
A generalisation to weighted network and a redefinition to two-mode network.

             _{3x number of ʳ}
C = ^{_______________________________
             total number of triplets}


 

Definition by Example

clustering coefficient of the 🔵 is computed as the proportion of connections among its neighbours which are actually realised compared with the number of all possible connections.

center: the 🔵 has 3 neighbours, hence it can have a maximum of 3 connections as indicated by the 3 blue solid lines,
hence local clustering coefficient = 1

right: the 🔵 has only 1 connection realised as indicated by the 1 blue solid lines, and & the other 2 missing connections as indicated by 2 orange dotted lines, hence local clustering coefficient = ⅓

left: none of the possible connections among the neighbours of the 🔵 are realised, as indicated by the 3 orange dotted lines, hence local clustering coefficient = 0

Definition

The Local Clustering Coefficient of a vertex (node) in a graph quantifies the closeness of its neighbours are to being a clique viz: a complete graph

A graph G =(V, E) is defined as a set of vertices V & a set of edges E between these vertices.

An edge, e _ij connects vertex v_i with v_j

k_i = number of vertices

|N_i|, in the neighborhood N_i, of a vertex v_i

The neighbourhood, N_ij for a vertex v_i is defined as its immediate connected neighbors as:

N _i = { v_j: e_ij∊E ∨ e_ji∊E}

The Local Clustering Coefficient, C_i, in the neighbourhood, of a vertex v_i :

         _{proportion of links between the vertices within its neighbourhood}
C_i= ^{___________________________________________________________________
               number of links that could possibly exist between them}

Undirected Graph

In an undirected graph, e_ij≡e_ji    k_i(k_i-1)
If a vertex v_i has k_i neighbors & ^__________ edges
                                                               ²
∴ the Local Clustering Coefficient, C_i

           2|{ e_jk: v_j, v_k∊N_i, ∨ e_ji∊E}|
C_i= ^{________________________________________
                     k_i(k_i-1)}

Directed Graph

directed graph, is a distinct form, whereby: ∴ ∨ neighbourhood links, ∵ among the vertices within the neighbourhood = the number of neighbours of a vertex.

In a directed graph, e_ij≠e_ji

∨ neighborhood N_i ∃ k_i(k_i -1) links ∀ vertices in that neighborhood.

∴ the Local Clustering Coefficient, C_i

           |{ e_jk: v_j, v_k∊N_i, ∨ e_ji∊E}|
C_i= ^{______________________________________
                     k_I(k_I-1)}

Average Clustering Coefficient

As an alternative to Global Clustering Coefficient, the overall level of clustering in a network can also be measured by the average of the Local Clustering Coefficients of all the vertices n

          1  _n
C=^__∑C_i
         n  ⁱ⁼¹

a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction)