C comme clustering coefficient
Ces billets visent à définir le plus clairement et le plus précisément possible des termes clés en analyse de réseau. Ils s’adressent à un public débutant et évitent autant que possible toute formalisation mathématique (pour cette dernière, voir les synthèses fmr sur Hal-Shs).
Le clustering coefficient est une mesure permettant d’évaluer le niveau de transitivité local ou global d’un graphe. En d’autres termes, on étudie les liens au niveau des triades – relations entre trois sommets – et l’on vérifie si, lorsqu’il existe un lien entre les sommets ab et bc, il existe également un lien entre les sommets a et c, suivant en cela l’expression populaire “les ami-es- de mes ami-es- sont mes ami-e-s”.
La formule du clustering coefficient global est simple (nombre de triangles X 3 / nombre de triades connexes) et son interprétation aisée : l’indicateur varie entre 0 et 1, 0 dans le cas d’arbres par exemple, 1 quand chaque sommet appartient à une clique. Le terme triangle désigne une triade fermée. Le clustering coefficient local d’un sommet i est le rapport entre le nombre de sommets voisins de i reliés les uns aux autres et le nombre de paires de voisins de i. Un lien manquant localement dans une triade de sommets est appelé trou structural.
Soit le graphe ci-dessous :
Le clustering global est égal à 0.6. En effet, il y a 2 triangles – à multiplier par 3 – et 10 triades connexes (123, 231, 312, 345, 453, 534, 134, 135, 234 et 235). Le clustering local des sommets 1, 2, 4 et 5 est égal à 1 – leurs voisins sont connectés les uns aux autres. Le sommet 3 a un clustering coefficient égal à 0.33 : il a 4 voisins mais, sur les 6 triades possibles (123, 143, 153, 234, 235, 345), seules 2 sont présentes (123 et 345).
Dernier point : le clustering coefficient est une mesure proposée par les physiciens au début des années 90 mais qui reprend exactement le sens et la formule de la transitivité utilisée depuis les années 70 en analyse des réseaux sociaux.
Billets liés : A comme arbre, C comme clique, T comme triade, T comme trou structural.
Script R :
library(igraph)
g <- rbind(c(1,2), c(1,3),
c(2,3), c(3,4),
c(3,5), c(4,5))
g <- graph.data.frame(g, directed=FALSE)
plot(g)
transitivity(g, type=c("globalundirected"))
transitivity(g, type=c("localundirected"))
OpenEdition vous propose de citer ce billet de la manière suivante :
Laurent Beauguitte (17 juin 2014). C comme clustering coefficient. groupe fmr (flux, matrices, réseaux). Consulté le 19 janvier 2025 à l’adresse https://doi.org/10.58079/p83j
1 réponse
[…] liés : C comme clustering coefficient, T comme trou […]