title: Coefficient de clustering
text: # 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.
  
  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
  
  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
  
  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.
  
  