C comme clique/cluster/commmunauté

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).

Pour analyser un réseau, trois grands types de méthodes existent : étudier les caractéristiques des sommets et, plus rarement, des liens (mesures locales) ; étudier les caractéristiques du graphe dans son ensemble (mesures globales) et enfin chercher des partitions pertinentes permettant de regrouper des sommets. La recherche de cliques appartient à cette dernière catégorie.

La définition de la clique est ancienne (années 50) : il s’agit d’un sous-graphe maximal complet d’au moins trois sommets. En clair, il s’agit du plus grand ensemble possible de sommets au sein d’un graphe entre lesquels tous les liens possibles sont présents. Dans la figure ci-dessous, on distingue trois cliques {abc}, {bcd} et {fgh}. Comme on le voit, un sommet peut appartenir à plusieurs cliques.

Cliques

Cette méthode présente au moins deux inconvénients. Tout d’abord, la définition est très restrictive : si un seul lien manque, il n’y a pas de clique. Dans la figure ci-dessus, le sous-graphe {abcd} n’est pas une clique car il manque un lien entre a et d. Différentes méthodes ont donc été proposées pour assouplir cette définition (voir k comme k-plex et k-core). Ensuite, si la méthode est adaptée à des graphes comprenant quelques dizaines de sommets, elle devient inutilisable pour des graphes plus imposants. Les physiciens et les informaticiens travaillant généralement sur des graphes beaucoup plus volumineux ont donc proposé des méthodes alternatives permettant de déceler ces sous-graphes d’acteurs fortement connectés les uns ou autres : utiliser la centralité d’intermédiarité des liens (voir C comme centralité(s)), mobiliser la modularité pour évaluer la qualité d’une partition.

Si les termes différent selon les communautés scientifiques, cliques, clusters et communautés désignent ces sous-graphes fortement connectés. En fonction de la thématique et des données étudiées, ces ensembles peuvent renvoyer à des concepts différents : liens forts et faibles ou structure centre – périphérie notamment.

Pour aller plus loin : Cliques, communautés et dérivées sur hal-shs.

Billets liés : C comme centralité(s), k comme k-core et k-plex.

Retour au glossaire


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *