k comme k-core et k-plex

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

La recherche de sous-graphes de sommets densément connectés, et nommés selon les disciplines cliques, clusters ou communautés, est l’un des objectifs privilégiés de  l’analyse de réseaux. Outre les cliques, abordées dans un billet précédent, de nombreuses méthodes existent et deux sont ici abordées : la recherche des k-cores et celle des k-plexes.

Un k-core est un sous-graphe où chaque sommet est adjacent à au moins k autres sommets de ce sous-graphe. La valeur de k est fixé par le ou la chercheur-e en fonction de la densité du graphe étudié. Cela revient à assouplir la définition de la clique en imposant une contrainte relative au nombre de liens devant être présents. Un k-plex est un sous-graphe maximal (i.e. on ne peut ajouter de sommets sans qu’il ne perde ses propriétés) contenant g sommets dont chaque sommet est adjacent à au moins g – k sommets de ce sous graphe, les valeurs de g et k étant fixées par le ou la chercheur-e. Autrement dit, quand le k-core fixe un nombre minimum de liens devant être présent, le k-plex autorise un certain nombre de liens à être absents. Si la démarche peut sembler proche, les résultats sont différents.

Dans le graphe ci-dessous, si l’on recherche les k-plexes d’au moins quatre sommets (g = 4) où 2 liens peuvent manquer (k = 2), on  trouve le seul quadruplé {abcd} : chacun de ces sommets est relié à au moins 2 autres sommets (4-2) de ce sous-graphe.  Si k est fixé à 1, cela revient à rechercher les cliques présentes dans le graphe. La recherche des k-cores où k = 2 donne les sous-graphes {abcd} et {fgh} : dans les deux cas, chacun des sommets est relié à au moins deux autres sommets de ces ensembles. Toute clique est donc également un k-core, l’inverse n’étant évidemment pas vrai.

Recherche de  k-core et de k-plex

De nombreuses autres adaptations des cliques ont été proposées au fil des décennies (n-clan, n-clique, LS sets, Lambda sets etc.) mais il est rare qu’elles soient implémentées dans les logiciels d’analyse de réseaux. Ucinet est sans doute le logiciel proposant le plus de variantes sur cet aspect.

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

Billets liés : C comme clique/cluster/communauté

Retour au glossaire



Citer ce billet
Laurent Beauguitte (2013, 12 septembre). k comme k-core et k-plex. groupe fmr (flux, matrices, réseaux). Consulté le 27 mai 2024, à l’adresse https://doi.org/10.58079/p833

Vous aimerez aussi...

Laisser un commentaire

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

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur comment les données de vos commentaires sont utilisées.

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search