Coefficient de clustering

alt=|vignette|Un graphe de fort 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 ? Il existe deux définitions différentes du coefficient de clustering : une version globale et une version locale. alt=|vignette|Graphe de coefficient de clustering : c'est la proportion de paires de voisins connectés dans le graphe.Le coefficient de clustering global est défini comme : où un triangle est une clique de trois nœuds. Le nombre de paires de voisins distincts d'un nœud de degré étant égal à , on obtient : où est le degré du nœud et l'ensemble des nœuds du graphe. On a , 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é). vignette|Noeud de coefficient de clustering (en rouge). C'est la proportion de ses paires de voisins connectés. Le coefficient de clustering local d'un nœud est défini comme : soit C'est la fraction de ses paires de voisins connectés, égale à 0 si par convention. On a , avec égalité si et seulement si le nœud 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 : On a également , avec égalité si et seulement si le graphe est un ensemble de cliques de taille au moins 3. 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é.