Tout est graphe ! Détection de communautés : théorie et retour d’expérience

Après un premier article introductif à la théorie des graphes, notre série continue avec la détection de communautés. En effet, ce domaine offre de nombreux cas d’application (détection de fraude, RH analytics..) et la recherche y est florissante : dynamique temporelle des réseaux, multi-appartenance communautaire, métriques de performance… Cet article vise à donner une première vue d’ensemble des algorithmes et outils existants, ainsi qu’un retour sur leur utilisation pratique. Des illustrations seront également données à partir de données LinkedIn.

1. QU’EST-CE QU’UNE COMMUNAUTÉ ?

Une communauté se définit par rapport à un graphe courant comme un groupe de nœuds qui sont particulièrement reliés entre eux et faiblement reliés au reste du réseau. Il peut s’agir par exemple d’individus qui échangent beaucoup entre eux et peu avec les autres. Il est particulièrement intéressant d’identifier ces groupes afin de faire émerger la structure sous-jacente du graphe. On peut ainsi le diviser en groupes naturels d’individus (sans chevauchement, i.e. un nœud appartient à un unique groupe) qui peuvent être de toute taille. Cette identification va prendre en compte uniquement la structure du graphe, ainsi que les éventuels poids d’arêtes qui apportent de l’information supplémentaire, par exemple le niveau d’activité d’une relation.

2.  QUELS ALGORITHMES DE DÉTECTION ?

L’approche traditionnelle est de minimiser le taux de coupe (i.e le nombre d’arêtes inter-communautés) en réalisant un partitionnement, avec comme inconvénient principal de devoir choisir en amont le nombre de communautés.

Par la suite, une approche alternative visant à trouver des sous-groupes densément connectés s’est répandue, avec comme avantage de pouvoir sélectionner automatiquement le nombre de groupes. Elle comprend notamment les approches de maximisation de modularité, définie ci-dessous.

L’ensemble de ces approches sont non supervisées, on n’apprend pas à partir de communautés déjà labellisées.

Partitionnement par coupe d’arêtes

Clustering spectral : on souhaite partitionner en se basant sur un critère de coupe, i.e en coupant les arêtes ayant un poids faible, avec un choix ex-ante du nombre de communautés.

Etape 1 : On calcule la matrice Laplacienne, qui se définit telle que : L = D − A où D est la matrice des degrés, et Ala matrice d’adjacence. Il convient de la normaliser en cas de forte hétérogénéité des degrés.

Etape 2 : On calcule alors les k vecteurs propres de L correspondant aux k plus petites valeurs propres.

Etape 3 : On effectue un k-means sur la matrice contenant en colonnes les k vecteurs propres.

Girvan Newman (2008) utilise la edge-betweenness pour déduire des groupes. C’est le corollaire de la betweenness de nœud (ou intermédiarité), qui est une mesure de centralité : sur combien de plus courts chemins mon nœud est-il positionné ?

Girvan Newman étend cette notion aux arêtes. Cet algorithme offre des résultats de qualité et un raisonnement intuitif.

Etape 1 : On calcule la edge-betweenness de l’ensemble des arêtes

Etape 2 : Les arêtes avec la plus forte edge-betweeness, i.e qui ont le plus de chances d’être des ponts entre communautés, sont supprimées.

Etape 3 : Ces deux étapes sont répétées.

Le principal inconvénient est une forte complexité algorithmique, ce qui limite son usage à de petits graphes.

Identification de sous-groupes denses

La modularité Q est un score ∈ [−1; 1] (Newman 2006) qui compare, pour un groupe de nœuds, le nombre d’arêtes réel par rapport au nombre d’arêtes espéré (dans un réseau équivalent où les arêtes sont placées de façon aléatoire). S’il y a plus d’arêtes qu’espéré, alors on pourrait avoir un groupe. On obtient ainsi un score de division d’un réseau en modules (nos communautés).

Il est donc fréquent d’utiliser sa maximisation pour identifier des structures communautaires. Cependant, le problème exact de maximisation est NP complet, et par conséquent peu applicable sur des graphes de taille significative. Une version approximée a été publiée en 2004 par Clauset et al. : Fastgreedy (2004). Il fusionne de façon itérative les nœuds puis les groupes de nœuds ensemble de façon à optimiser la modularité globale de la structure communautaire, et crée ainsi un dendrogramme, qui est ”coupé” là où la modularité est maximale. Sur un graphe à n nœuds et m arêtes, sa complexité est de O(mdlogd) où d est la profondeur du dendrogramme qui décrit la structure communautaire.

Cependant, un problème a été identifié : la limite de résolution. Optimiser la modularité globale ne permets pas toujours d’identifier la structure communautaire d’un graphe sous l’hypothèse (souvent vérifiée) que la taille des groupes est très hétérogène. Fastgreedy a alors tendance à agréger des petits groupes d’individus en une super-communauté avec une faible cohérence interne. Cela pose deux problèmes : trouver les bonnes communautés, et le temps de calcul ralenti par ces agrégations superflues (compliqué pour plus d’un million de nœuds).

Des méthodes de résolution à multiples niveaux ont par conséquent été développées, et en particulier l’algorithme de Louvain, publié en 2008 par Blondel et al. Ici, on maximise la modularité locale, c’est à dire la modularité du groupe, et non pas de la structure communautaire.

Etape 1 : Chaque nœud est sa propre communauté. Pour chaque nœud, on cherche là où il augmente le plus la modularité du groupe, s’il existe un gain positif. On s’arrête lorsqu’il n’y a plus de gain possible. Un maximum local est alors atteint.

Etape 2 : on réitère en considérant une communauté comme un nœud. On stoppe lorsqu’il n’y a plus de gain positif issus de la fusion des communautés.

Ces deux étapes sont réitérées, en général 2-3 fois maximum, et on obtient un partitionnement final avec des communautés de tailles potentiellement très hétérogènes.

Louvain est un algorithme que l’on peut raisonnablement conseiller d’utiliser en première intention, en particulier sur des graphes de grande taille (plusieurs millions de nœuds, dizaines ou centaines de millions d’arêtes).

D’autres algorithmes existent et peuvent être tout aussi efficaces que les méthodes présentées précédemment. L’algorithme Walktrap (Pons, Latapy 2005), utilise une mesure de similarité entre nœuds basée sur des marches aléatoires. L’intuition est la suivante : une marche aléatoire a tendance à rester piégée au sein des communautés d’un graphe. Ainsi, elle est révélatrice de la structure du graphe et peut être utilisée pour comparer des nœuds : si le chemin de la marche aléatoire partant d’un nœud i est similaire à celui d’un nœud j, alors les deux nœuds ont une probabilité significative d’appartenir à la même communauté. On peut alors agréger de façon itérative comme pour l’algorithme Fastgreedy, et couper le dendrogramme là où la modularité est maximale.

Infomap (Rosvall et Bergstrom, 2008) et Label Propagation (Raghavan et al., 2007) sont également deux alternatives à considérer. Cependant, leurs performances n’étaient pas supérieures à d’autres algorithmes tels que Walktrap –dans les tests que j’ai pu réaliser- tout en étant moins intuitifs.

Attribution de multiples communautés à un nœud

Un algorithme attribue chaque nœud du graphe G à une unique communauté. Or, dans la vraie vie, un nœud peut, et va, appartenir à plusieurs groupes. Une solution de contournement peut être de passer au line graph L(G), où chaque nœud de L(G) est une arête de G et deux nœuds de L(G) sont connectés si et seulement si les deux arêtes qu’ils représentent ont un nœud commun. Par exemple, un graphe de trois nœuds, Alberto, Ysé et Adèle, avec une relation Alberto-Adèle et Ysé-Adèle, sera transformé en un line graph à deux nœud (Alberto-Adèle, Ysé-Adèle), qui auront une arête, car Adèle est une connaissance commune.

Appliquer les algorithmes de détection de communautés sur L(G) permet donc d’attribuer plusieurs communautés à un nœud, une fois revenus dans l’espace de G. On aura par conséquent un ”clustering d’arêtes” de G. Ici on voit un graphe généré, avec une application de ce clustering d’arêtes. On peut observer que plusieurs nœuds ont des arêtes de communautés différentes.

Quels algorithmes choisir ?

En première intention, pour les approches de maximisation de modularité, il convient de préférer Louvain à Fastgreedy, en raison de la limite de résolution et d’une scalabilité bien meilleure (plusieurs millions de nœuds et centaines de millions d’arêtes en 13 minutes sur une Qbox par exemple). Louvain fait d’ailleurs partie des algorithmes de détection de communauté les plus rapides (plus que Walktrap par exemple).

Quels outils ?

Plusieurs outils peuvent être envisagés :