Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain

Chapitre 2. Les algorithmes de création de communautés

Les différents algorithmes se différencient sur la manière de détecter les liaisons à supprimer pour créer la scission.

Détection des liaisons à forte centralité	Suppression des liaisons à forte centralité	Détection des communautés

^Y

B

^Z

^A

^C

^W

^Y

^X

^Z

Figure 2.2 : Illustration de la méthode de M. E. J. Newman and M. Girvan pour créer des communautés

basées sur des composantes connexes créées par le retrait de liaisons à forte centralité.

La méthode de Girvan et Newman illustrée figure 2.2, se fonde sur la recherche de liaisons où la centralité est la plus élevée (Liaisons où passe un maximum de chemins « le plus court » pour aller d'un noeud à un autre) [Newman-2004-3].

^{A W}

C

^B cB(e)=32

^{X Y}

^D Z

^{A W}

^C

^X

^D

^R

^D

2.2.3 Les algorithmes de recherche de zones de forte modularité

Les algorithmes de recherche de zones de forte modularité s'appuient sur la notion de modularité introduite par Newman en 2004 [Newman-2004-2]. Ils cherchent, en se basant sur la définition d'une communauté en tant qu'élément dense du réseau, à déterminer des zones prédisposées à devenir des communautés. Pour un découpage en communautés données par un algorithme, la modularité est la différence entre la part d'arêtes intra-communautaires et la même valeur pour une répartition aléatoire des arêtes pour le graphe complet étudié. Avec une variation comprise entre -1 et 1, plus la modularité est élevée plus les communautés sont de qualité.

Finalement assez proche de la définition de la communauté « forte » donnée par Fortunato « Une communauté forte est telle que le degré de chaque noeud interne est supérieur à son degré externe » [Fortunato-2010], les algorithmes utilisant la recherche d'une forte modularité pour définir des communautés sont très nombreux. Nous pouvons donner, à titre d'exemple, le travail de Fabrice Rossi et Nathalie Villa-Vialaneix sur l'application de ce principe sur les réseaux topologiques [Rossia&al-2010]. On peut aussi noter que cette démarche, est devenue une démarche de référence. En effet, on la retrouve dans bien des logiciels permettant de travailler sur les graphes. Le logiciel R ( http://www.r-project.org/) présente dans sa librairie « Igraph » ( http://igraph.sourceforge.net) une fonction « modularity » permettant de retourner la capacité d'un sous-graphe à devenir une communauté de « qualité ».

En 2008, Newman a proposé une version de son algorithme capable de gérer les graphes pondérés [Newman&al-2008].

2.3. Les différentes méthodes de recherche de communautés avec recouvrement 55