Coefficient de clustering

En théorie des graphes et en analyse des réseaux sociaux, le coefficient de clustering d'un graphe (aussi appelé coefficient d'agglomération, de connexion, de regroupement, d'agrégation ou de transitivité), est une mesure du regroupement des nœuds dans un réseau. Plus précisément, ce coefficient est la probabilité que deux nœuds soient connectés sachant qu'ils ont un voisin en commun.

Un graphe de fort coefficient de clustering.

C'est l'un des paramètres étudiés dans les réseaux sociaux : les amis de mes amis sont-ils mes amis ?

Définitions

Il existe deux définitions différentes du coefficient de clustering : une version globale et une version locale.

Coefficient global

Graphe de coefficient de clustering $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 :

$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é $d$ étant égal à ${d \choose 2}$, on obtient :

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

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

On a $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é).

Coefficient local

Noeud de coefficient de clustering ${\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 $i$ est défini comme :

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

soit

$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 $d_{i}\leq 1$ par convention.

On a $C_{i}\leq 1$, avec égalité si et seulement si le nœud $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 :

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

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

Propriétés et variantes

Relation entre les deux versions et interprétation

Le coefficient global $C$ s'exprime à partir des coefficients locaux comme  :

$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 ${\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é. 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 $C$ s'interprète comme la probabilité que deux nœuds distincts soient connectés sachant qu'ils ont un voisin en commun.

Expression à partir de la matrice d'adjacence

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

$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 à $\sum _{i\in V}d_{i}(d_{i}-1)$.

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

Variantes

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

Modèle

Le modèle de Watts-Strogatz permet de générer des graphes aléatoires ayant à la fois un fort coefficient de clustering et la propriété dite de petit monde. Ces deux propriétés sont caractéristiques les grands graphes réels, comme ceux formés par les réseaux sociaux.

Historique

Le coefficient global est souvent attribué à Barrat et Weigt pour l'article On the properties of small-world network models publié en 2000. Le coefficient moyen local est attribué à Watts et Strogatz, pour l'article Collective dynamics of ‘small-world’ networks de 1998.

Voir aussi

• Trou structural
• Cohésion sociale
• Capital social

Bibliographie

• (en) Mark E.J. Newman, « The structure and function of complex networks », SIAM review, SIAM, vol. 45, n^o 2,‎ 2003, p. 167-256

• (en) Mason A. Porter, « Small-world network », dans Scholarpedia, 2014 (lire en ligne)

Liens externes

• Sriram Pemmaraju (scribes : Geoffrey Fairchild and Jason Fries), « Lecture Notes: Social Networks: Models, Algorithms, and Applications », sur Université d'Iowa, 2012