C’est devenu un rituel : j’assiste à une présentation d’analyste de réseaux, la personne présente un graphe touffu (pléonasme) avec plein de couleurs (et souvent des liens courbes) et explique que les couleurs représentent “les communautés détectées dans le graphe”. La présentation terminée, je lève la main et, si on me donne la parole, je signale que “les communautés dans le graphe”, ça ne veut rien dire… Petit point d’explication ci-dessous. Il s’agit d’un billet d’humeur individuel qui ne saurait représenter “le point de vue officiel du gdr sur le sujet ” (le gdr n’a de toute façon pas de point de vue officiel).

Le terme “communautés” est récent et date de l’arrivée des physicien.ne.s & informaticien.ne.s dans le champ de l’analyse de réseaux. Auparavant, on parlait de cliques, de k-plex, de k-cores, etc. Ces méthodes sont pertinentes pour de petits graphes mais perdent de leur efficacité à mesure que la taille des graphes augmente. D’où l’apparition du terme de communautés désignant de façon relativement floue des ensembles de sommets plus fortement connectés entre eux qu’avec les autres sommets du graphe.

Il existe des dizaines de méthodes permettant de détecter des communautés dans un graphe. Fortunato dans un article de 2010 recense plus de 50 méthodes ; Rémy Cazabet dans sa thèse indique que selon certains auteurs (qu’il ne cite malheureusement pas), il y aurait plus de 250 algorithmes de détection de communautés publiés (Cazabet, 2013, p. 16). Peu importe le nombre exact : ce n’est pas parce qu’un logiciel connu ne propose qu’une seule méthode de détection de communautés que cela autorise à parler “des communautés dans un graphe”. Surtout que le seul algorithme implémenté par défaut (il existe des modules additionnels permettant d’en implémenter d’autres) dans ce logiciel est non déterministe : en clair, le relancer plusieurs fois est susceptible de générer des résultats légèrement différents…

Les communautés dans un graphe n’existent pas : il existe des communautés détectées par tel algorithme avec tels paramètres et tel logiciel. Les quelques lignes qui suivent – et le script téléchargeable – rappellent quelques généralités sur la détection de communautés puis présentent rapidement les algorithmes disponibles avec igraph (package R bien connu d’analyse de réseaux).

La plupart des algorithmes créent des communautés non recouvrantes ; un sommet ne peut appartenir qu’à une communauté et une seule. Or, les recouvrements de communautés sont fréquents dans les réseaux empiriques.

La méthode proposée par Girvan et Newman (2002) repose sur un algorithme divisif, toutes les nœuds au départ appartiennent à une seule communauté. On retire un à un les liens ayant la centralité d’intermédiarité maximale jusqu’à rendre le graphe non connexe, chaque composante constituant une communauté. Les visions successives créent un dendrogramme puis on recherche le découpage qui optimise la modularité (cf infra).

D’autres méthodes sont de type agglomérative : au départ, chaque sommet constitue une communauté et ils sont agrégés deux à deux à chaque itération. Il est donc possible de produire un dendrogramme montrant les regroupements successifs. Là aussi, le nombre de classes est généralement fait pour maximiser la modularité Q. La modularité est la différence entre la proportion de liens à l’intérieur des communautés et la proportion de liens qui tomberaient à l’intérieur de ces mêmes communautés dans un graphe aléatoire de même distribution de degrés. Cette mesure varie entre 0 et 1 : plus elle est élevée, plus la partition est estimée pertinente.

Si je parvenais à mettre du LaTeX dans mon billet (ce qui est en théorie possible), je mettrais la formule ici. Comme je viens de perdre deux heures sans résultat, je renvoie vers le wikipedia anglophone…

Cette mesure a des limites : pour un réseau ayant une taille et une densité données, la modularité ne peut pas détecter de communautés inférieures à une taille donnée, même si de petites communautés nettement séparées existent dans le réseau étudié.

.D’autres mesures de la qualité de la partition ont été proposées. Cazabet (op. cit., p. 103 et sq) évoque par exemple la conductance, soit le rapport entre le nombre de liens sortants de la communauté et la somme des degrés de ses nœuds. Elle varie entre 0 (composante connexe) et 1 (communauté sans lien interne ou ayant une infinité de liens externes). Par contre, elle ignore la structure interne : deux communautés avec une conductance de 0.5 peuvent avoir des structures très différentes. D’autres métriques existent comme l’expansion (nombre de liens par nœud pointant hors du cluster) ; l’internal density (densité de liens internes du cluster), le cut ratio (fraction de tous les liens sortants possibles présents) etc.

Je résume : il n’existe pas une méthode de détection de communautés, et il n’existe pas non une mesure de la qualité de la partition obtenue. Le package igraph propose 9 algorithmes de partitionnement différents, algorithmes rapidement décrits ci-dessous. Pour plus d’informations, voir les aides des fonctions correspondantes.

Fonction cluster_edge_betweenness

Partitionnement fondée sur l’intermédiarité des liens : on mesure l’intermédiarité des liens, on supprime celui ayant la plus élevée et on répète l’opération jusqu’à rendre le graphe non connexe.

Fonction cluster_fast_greedy

On définit une grandeur notée Delta Qij qui correspond à la variation de la modularité quand on crée un lien entre la communauté i et la communauté j. Au départ, chaque sommet est une communauté ; on calcule Delta Qij pour toutes les paires, on fusionne les paires qui accroissent le plus la modularité, on répète jusqu’à obtenir une seule communauté puis on coupe le dendrogramme à la valeur correspondant à la plus forte modularité.

Fonction cluster_label_prop

Méthode proposée par Raghavan, U.N. and Albert, R. and Kumara, S.: Near linear time algorithm to detect community structures in large-scale networks, Physical Review E, 76, 036106, 2007. Chaque sommet se voit attribuer un label puis, par itération, les labels diffusent dans le réseau. Chaque sommet adopte le label le plus fréquent chez ses voisins.

Fonction cluster_leading_eigen

Méthode proposée par MEJ Newman: Finding community structure using the eigenvectors of matrices, Physical Review E, 74, 036104, 2006. On définit une matrice de modularité B telle que B=A-P où A est la matrice d’adjacence du graphe et P la probabilité que deux sommets soient voisins. Un élément P[i,j] de P est la probabilité qu’il existe un lien entre les sommets i et j dans un graphe aléatoire dont la distribution des degrés est équivalente au graphe étudié. Le calcul des vecteurs propres de la matrice B permet la partition des sommets en communautés. Comme l’indique la rubrique d’aide : “
Check Newman’s paper to understand why this is a good method for detecting community structure.”

Fonction cluster_louvain

Méthode très rapide et souvent utilisée, basée sur une approche locale de la modularité. Une communauté est attribuée à chaque sommet puis on s’intéresse aux voisins de chaque sommet i, et on calcule le gain de modularité en retirant le sommet i et en le plaçant dans la communauté j. On réitère l’opération jusqu’à ce qu’aucune amélioration ne soit possible. Méthode capable de détecter de petites communautés même dans de très grands graphes

Fonction cluster_optimal

Exploration de toutes les communautés possibles et maximisation de la modularité. Inutilisable pour les graphes de taille moyenne ou grande

Fonction cluster_spinglass

Voir J. Reichardt and S. Bornholdt: Statistical Mechanics of Community Detection, Physical Review E, 74, 016110, 2006. Méthode basée sur la recherche des graphes hamiltoniens (graphe possédant au moins un cycle passant par tous les sommets une fois au plus).

Fonction cluster_walktrap

Méthode proposée en 2005 par Pascal Pons et Matthieu Latapy dans l’article Computing communities in large networks using random walks, International symposium on computer and information sciences, Springer, pp. 284-293. En substance, on crée une marche aléatoire d’un sommet vers un autre. Plus le degré d’un sommet est élevé, plus la probabilité qu’il soit sur cette marche est élevée. Par ailleurs, si deux sommets ij sont dans la même communauté, une marche aléatoire au départ de i a une probabilité forte de passer par j. Au départ, chaque sommet est une communauté puis ils sont regroupés étape par étape jusqu’à former une seule communauté. Puis la mesure de la modularité permet de couper le dendrogramme pour obtenir la partition la plus adaptée

Fonction igraph_community_infomap

Algorithme de Rosvall et Bergstrom (2008), rapide, performant, adapté aux grands réseaux. Principe : on considère un marcheur aléatoire se déplaçant dans un réseau, si des communautés sont présentes, le marcheur tend à rester à l’intérieur de ces communautés. Si le graphe est aléatoire, il se déplacera partout montrant l’absence de communautés (différence importante avec les méthodes basées sur l’optimisation de la modularité qui trouvent toujours des communautés).

Affirmer en montrant une figure, les communautés du graphe sont les suivantes n’a pas de sens. Affirmer, en montrant une figure, les communautés détectées avec tel algorithme et en fixant un nombre de classes maximisant la modularité est correct. Voici par exemple huit partitions obtenues à l’aide d’algorithmes implémentés dans igraph sur le même jeu de données – le nom de l’algorithme est suivi de la modularité obtenue.

Références

Cazabet, R. (2013). Détection de communautés dynamiques dans des réseaux temporels. Thèse de doctorat. Université Paul Sabatier-Toulouse III. En ligne.

Fortunato, S. (2010). Community detection in graphs. Physics reports, 486(3-5), 75-174. En ligne.

---

---