Coefficient de clustering

Graphe de coefficient de clustering ${\displaystyle C={\frac {3}{4}}}$: c'est la proportion de paires de voisins connectés dans le graphe.

Le coefficient de clustering global est défini comme :

${\displaystyle C={\frac {3\times |{\mbox{triangles}}|}{|{\mbox{paires de voisins distincts}}|}}}$

où un triangle est une clique de trois nœuds.

Le nombre de paires de voisins distincts d'un nœud de degré ${\displaystyle d}$ étant égal à ${\displaystyle {d \choose 2}}$, on obtient :

${\displaystyle C={\frac {3\times |{\mbox{triangles}}|}{\sum _{i\in V}{d_{i} \choose 2}}},}$

où ${\displaystyle d_{i}}$ est le degré du nœud ${\displaystyle i}$ et ${\displaystyle V}$ l'ensemble des nœuds du graphe.

On a ${\displaystyle C\leq 1}$, avec égalité si et seulement si le graphe est un ensemble de cliques de taille au moins 3 (un graphe complet si le graphe est connecté).

Noeud de coefficient de clustering ${\displaystyle {\frac {2}{3}}}$ (en rouge). C'est la proportion de ses paires de voisins connectés.

Le coefficient de clustering local d'un nœud ${\displaystyle i}$ est défini comme :

${\displaystyle C_{i}={\frac {|{\mbox{triangles de sommet }}i|}{|{\mbox{paires de voisins distincts de }}i|}},}$

soit

${\displaystyle C_{i}={\frac {|{\mbox{triangles de sommet }}i|}{d_{i} \choose 2}}.}$

C'est la fraction de ses paires de voisins connectés, égale à 0 si ${\displaystyle d_{i}\leq 1}$ par convention.

On a ${\displaystyle C_{i}\leq 1}$, avec égalité si et seulement si le nœud ${\displaystyle i}$ et son voisinage forment une clique d'au moins 3 nœuds.

En prenant la moyenne des coefficients locaux, on obtient le coefficient local moyen :

${\displaystyle {\bar {C}}={\frac {\sum _{i\in V}C_{i}}{|V|}}}$.

On a également ${\displaystyle {\bar {C}}\leq 1}$, avec égalité si et seulement si le graphe est un ensemble de cliques de taille au moins 3.

Le coefficient global ${\displaystyle C}$ s'exprime à partir des coefficients locaux comme  :

${\displaystyle C={\frac {\sum _{i\in V}{d_{i} \choose 2}C_{i}}{\sum _{i\in V}{d_{i} \choose 2}}}.}$

C'est donc une moyenne pondérée des coefficients locaux, qui diffère du coefficient local moyen ${\displaystyle {\bar {C}}}$, sauf cas particuliers (graphe régulier par exemple). Les nœuds de fort degré ont donc plus de poids que ceux de faible degré[1]. Les poids reviennent à sélectionner un nœud en proportion du nombre de ses paires de voisins distincts, de sorte que le coefficient de clustering global ${\displaystyle C}$ s'interprète comme la probabilité que deux nœuds distincts soient connectés sachant qu'ils ont un voisin en commun.

En notant ${\displaystyle A}$ la matrice d'adjacence du graphe, matrice binaire dont l'entrée ${\displaystyle i,j}$ est égale à 1 si et seulement si les nœuds ${\displaystyle i,j}$ sont voisins, le coefficient de clustering s'écrit :

${\displaystyle C={\frac {\sum _{i\neq j\neq k}A_{ij}A_{ik}A_{jk}}{\sum _{i\neq j\neq k}A_{ij}A_{ik}}}.}$

En effet, le numérateur est égal à 6 fois le nombre de triangles et le dénominateur est égal à ${\displaystyle \sum _{i\in V}d_{i}(d_{i}-1)}$.

En l'absence de boucles (diagonale de ${\displaystyle A}$ nulle), le numérateur est la somme des éléments diagonaux de la matrice ${\displaystyle A^{3}}$ et le dénominateur la somme des éléments non-diagonaux de la matrice ${\displaystyle A^{2}}$.

Il existe des versions du coefficient adaptées à certains types de graphes, comme les graphes pondérés[2] ou les graphes bipartis[3].