User Tools

Site Tools


pennarun_mourany:claire_pennarun_alexandre_mourany

Visual Analytics Course

Bordeaux roadmap 2013- 2014 / Claire Pennarun & Alexandre Mourany's corner

Algorithme de Louvain

Présentation de l’algorithme

Idée générale

L’objectif de cet algorithme est de pouvoir décomposer un réseau en sous réseaux (ou communautés). Grâce à cela il est possible de découvrir des communautés ayant un sens dans un réseau, comme par exemple des sujets dans des réseaux d’informations ou des cyber-communautés dans des réseaux sociaux. L’algorithme fonctionne en regroupant ensemble les nœuds fortement connectés et en séparant les nœuds plus faiblement connectés.

Détail de l’algorithme

L’algorithme se décompose en 2 étapes qui sont répétées jusqu'à ce qu’il n’y ait plus de changements (la modularité du graphe sera alors maximale)

1ère étape
  • On assigne une communauté à chaque nœud
  • Tant qu’il y a un gain de modularité positif sur un des nœuds :
    • Pour chaque nœud i :
      • On récupère les voisins de i
      • Pour chaque voisin j de i, on calcule le gain de modularité Q ayant lieu si on enlève i de son cluster (c_i) et qu’on le met dans le cluster de j (c_j).
      • Si le max de ses gains (pour un certain voisin j’) est positif, on déplace i dans c_j’ (et on l’enlève de c_i). Si le max est négatif, on laisse i dans sa communauté.
2ème étape : construction d’un nouveau graphe
  • Construction d’un nœud pour chaque communauté créée dans la première phase
  • Nouveaux poids d’arêtes : calculés en faisant la somme des poids entre les nœuds de départ
  • Arêtes entre les nœuds d’un même nouveau nœud : on calcule la somme de leur poids et elles deviennent des boucles (loops)

Approche et implémentation

Gestion des poids

Tulip ne permettant pas de gérer des arêtes pondérées, nous avons utilisé une IntegerProperty pour stocker le poids des arêtes. Nous avons considéré que les arêtes avaient comme poids 1 au début de l’algorithme (leur poids va de toute façon augmenter au fur et à mesure des itérations). La propriété “weights” nous permet donc de stocker les poids de chaque arête, mais aussi les poids des sommets, qui sont la somme du poids interne et du poids des arêtes adjacentes.

Les communautés (clusters) possèdent également un poids interne (les poids des arêtes entièrement dans la communauté) et un poids total (les poids des arêtes dont l’une des extrémités au moins est dans la communauté). Ces informations sont représentées par des champs dans la classe Cluster.

Nous avons choisi de séparer l’implémentation de l’algorithme en deux étapes :

Création du nouveau graphe

Nous avons choisi de modéliser le passage d’une itération à la suivante par la création d’un nouveau graphe dont les noeuds seraient des métanoeuds représentant chaque communauté trouvée pendant l’itération. Nous avons testé notre construction en créant des communautés qui regroupent les deux noeuds du graphe les plus proches et en itérant jusqu’à ne plus avoir que deux noeuds.

A la fin du calcul des communautés dans le graphe G, deux sous-graphes de G sont créés : clustering et quotient. Le graphe clustering contient des sous-graphes qui représentent chacun une communauté créée dans G. Le graphe quotient est peuplé avec des métanoeuds créés avec la méthode createMetaNodes(), appelée sur l’itérateur des sous-graphes de clustering.

Les poids des arêtes internes à une communautés sont ajoutés et donnés comme “poids interne” au nouveau noeud représentant cette communauté dans quotient. Les poids des arêtes présentes entre deux communautés sont ajoutés et permettent de créer de nouvelles arêtes entre les noeuds du graphe quotient, arêtes qui auront des poids dépendant des anciennes arêtes sous-jacentes. Enfin, pour tous les noeuds du graphe quotient, les poids de ses arêtes adjacentes sont ajoutés à son propre poids.

L’algorithme est ensuite rappelé sur le graphe quotient.

Modularité

Nous avons ensuite implémenté une partie de l’algorithme de Louvain en nous concentrant tout d’abord sur le calcul de modularité. Lors de cette partie nous avons été confronté à un problème : la formule permettant de calculer le « gain » de modularité lorsque l’on sort un nœud de sa communauté n’était pas fournie dans l’article, nous avons du la retrouver à partir de la formule donnée pour le cas où on ajoute un nœud dans une communauté.

Gain de modularité en enlevant i de sa communauté

Implémentation finale

Nous avons enfin mis ensemble les deux implémentations effectuées précédemment. Après chaque itération de l’algorithme, la modularité du graphe est testée avec la fonction computeModularity() et affichée. L’algorithme s’arrête d’itérer lorsque plus aucun noeud du graphe ne change de communauté.

Résultats

Communautés :

Nous avons obtenu le même résultat (en terme de communautés, de poids des arêtes et des sommets) que les auteurs pour la première itération sur le graphe donné en exemple

Le résultat de notre première itération

Nous avons aussi testé notre algorithme sur un graphe composé de cliques :

La première itération retrouve les petites cliques de taille 4

Malheureusement, l’itération suivante ne retrouve pas les cliques de taille 3 (peut-être parce que cet algorithme repère “mal” les cliques de taille < 4 ?)

Modularité :

Contrairement aux communautés trouvées, les valeurs des modularités successives n’ont pas été données par les auteurs. Cependant, elles paraissent cohérentes : la modularité des graphes correspondant aux communautés successives du graphe de cliques est la plus importante après la première itération (0.33) et plus faible ensuite (0.02 puis 0.01)

/net/html/perso/melancon/Visual_Analytics_Course/data/pages/pennarun_mourany/claire_pennarun_alexandre_mourany.txt · Last modified: 2014/01/16 17:22 by amourany