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.
C'est l'un des paramètres étudiés dans les réseaux sociaux : les amis de mes amis sont-ils mes amis ?
Le coefficient global s'exprime à partir des coefficients locaux comme :
C'est donc une moyenne pondérée des coefficients locaux, qui diffère du coefficient local moyen , 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 s'interprète comme la probabilité que deux nœuds distincts soient connectés sachant qu'ils ont un voisin en commun.
En notant la matrice d'adjacence du graphe, matrice binaire dont l'entrée est égale à 1 si et seulement si les nœuds sont voisins,
le coefficient de clustering s'écrit :
En effet, le numérateur est égal à 6 fois le nombre de triangles et le dénominateur est égal à .
En l'absence de boucles (diagonale de nulle), le numérateur est la somme des éléments diagonaux de la matrice et le dénominateur la somme des éléments non-diagonaux de la matrice .
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[4],[5]. Ces deux propriétés sont caractéristiques des grands graphes réels, comme ceux formés par les réseaux sociaux[6].
Le coefficient global est souvent attribué[7] à Barrat et Weigt pour l'article On the properties of small-world network models publié en 2000[4]. Le coefficient moyen local est attribué à Watts et Strogatz, pour l'article Collective dynamics of ‘small-world’ networks de 1998[5].
↑M. Latapy, C. Magnien et N. Del Vecchio, « Basic Notions for the Analysis of Large Two-mode Networks », Social Networks, vol. 30, no 1, , p. 31-48 (DOI10.1016/j.socnet.2007.04.006)
↑ a et bAlain Barrat et Martin Weigt, « On the properties of small-world network models », The European Physical Journal B-Condensed Matter and Complex Systems, Springer, vol. 13, no 3, , p. 547-560
↑ a et bDuncan J. Watts et Steven H Strogatz, « Collective dynamics of ‘small-world’networks », Nature, Nature Publishing Group, vol. 393, no 6684, , p. 440-442