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

2.3.2 Les méthodes en plusieurs phases

Les méthodes utilisant plusieurs phases sont généralement les méthodes qui vont, dans une phase de départ, rechercher un noyau ayant une très forte modularité. Ces zones vont être les parties non partagées des communautés. Ensuite, d'autres phases auront pour objectif d'enrichir ces zones noyaux de noeuds adjacents, les noeuds adjacents pouvant alors constituer des zones partagées entre plusieurs communautés.

Détection et enrichissement de noyaux

La méthode présentée par Shang, Chen et Zhou [Shang&al-2007] se déroule en trois phases au cours desquelles les noyaux sont détectés puis enrichis (cf. figure 2.7) :

1. la recherche des communautés « noyaux » de petite taille extrêmement connectée ;

2. la fusion de certaines communautés élémentaires en communautés plus importantes ;

3. l'expansion de chaque communauté aux noeuds périphériques.

Phase 1 : Détection des communautés « noyaux »	Phase 2 : Fusion des communautés proches	Phase 3 : Expansion des communautés

Figure 2.7 : Les trois phases de la méthode proposée par Shang et al.

La première phase consiste simplement en un repérage des ensembles de noeuds formant une k-clique telle que la clique de type (k+1)-clique contenant la clique précédente n'existe pas.

La deuxième phase va conduire à fusionner deux cliques s'il existe entre ces cliques une connectivité supérieure à une valeur prédéterminée.

La troisième phase, qui va permettre à plusieurs communautés d'être en recouvrement, visera à ajouter à une ou plusieurs communautés les noeuds qui n'appartiennent à aucune communauté. Tout noeud présentant une connectivité supérieure à une valeur prédéterminée

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

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

vers une ou des communautés sera considéré comme faisant partie de cette ou de ces communautés.

La méthode nous semble présenter beaucoup d'avantages ; en premier lieu, sa simplicité et sa capacité à évoluer, Elle est, par exemple, facilement applicable à des graphes pondérés. Les phases pourront alors évoluer pour tenir compte des spécificités de la nature d'un graphe. De plus, la recherche de noyaux est réalisable par des algorithmes différents, permettant un recouvrement entre noyaux. Les noeuds reliés par un seul lien à un noeud participant à une communauté peuvent rejoindre la dite communauté et limiter le nombre de noeuds hors communautés. La phase finale d'expansion peut, elle aussi, être adaptée selon la nature des objets.

Création de communautés puis affinage

Peu avant la publication des travaux menés par Palla, en 2009, Jeffrey Baumes, Mark Goldberg, Mukkai Krishnamoorthy, Malik Magdon-Ismail et Nathan Preston présentaient l'article « Finding Communities by Clustering a Graph into Overlapping Subgraphs » [Baumes&al-2005-1]. Cet article décrit deux nouveaux algorithmes permettant de dégager d'un graphe un ensemble de communautés.

Les auteurs font appel à la notion de « PageRank » pour mesurer l'importance d'un noeud dans un graphe. La notion de « PageRank » a été définie initialement par Page et al. en 1998 pour mesurer l'importance relative d'un site web dans Internet par rapport aux liens qu'il possède avec les autres sites [Page&al-1998].

Le calcul du PageRank utilisé est basé sur la formule générale suivante :

( v) =c ? PR( u)

Nu

ou PR(v) est le PageRank du noeud v,

Bu est l'ensemble des noeuds voisin de v,

u est un des éléments de Bu, soit un voisin de v,

PR(u) est le PageRank du noeud u,

Nu est le degré de u,

et c un facteur de normalisation (choisi pour que la somme des « PageRank »

soit une constante).

Il est utile de préciser que Page et al. définissent le « PageRank » sur un graphe dirigé et pondéré. Les liaisons signifiant l'existence d'un lien d'un site web vers un autre. Elles sont unilatérales et peuvent être plus ou moins nombreuses. Nu est alors défini comme le poids de l'ensemble des liens sortants du noeud u et Bu est alors l'ensemble des noeuds ayant un lien vers le noeud v [Page&al-1998].

Le calcul du « PageRank » est issu d'un algorithme récursif. Cet algorithme ne possède pas toujours de point d'arrêt, puisque chaque « PageRank est dépendant du

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

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

« PageRank » de ses voisins. Pour trouver le PageRank de l'ensemble des noeuds, on initialise arbitrairement R(u') = 1 pour tous les noeuds u' du graphe. Puis on recalcule l'ensemble des « PageRank » du graphe, jusqu'à une convergence ou une certaine stabilité des résultats.

La méthode de création de communautés avec recouvrement proposée par Jeffrey Baumes et al. [Baumes&al-2005-1] s'articule autour de deux algorithmes :

? L'algorithme RaRe (Rank Removal) (cf . Figure 2.8) qui permet d'isoler un ensemble de noyaux de communautés. Pour cela, l'algorithme recherche les noeuds les plus « importants » (en utilisant, par exemple, le PageRank) et les retire du graphe de manière à ne conserver qu'un ensemble de petites composantes connexes. Ces composantes connexes donc deviennent les communautés. Les noeuds « importants » sont alors rajoutés tour à tour à ces composantes connexes pour finaliser les communautés et mettre en place les recouvrements.

? L'algorithme IS (Iterative Scan) qui permet de construire une partition du graphe localement optimale au sens de la densité. Il permet donc de raffiner les résultats obtenus avec l'algorithme RaRe de manière à obtenir une meilleure décomposition du graphe en communautés. Le principe de l'algorithme IS est simple : partant d'un ensemble de communautés racines (celles données par RaRe), un noeud quelconque du graphe est ajouté ou retiré à la communauté à chaque itération tant que la densité augmente.

Phase 1 : Détection des noeuds les plus importants	Phase 2 : Création des communautés sur la base des composantes connexes	Phase 3 : réintégration des noeuds importants et création des communautés avec recouvrement

Figure 2.8 : Les trois phases de la méthode RaRe.

Même si la combinaison des algorithmes RaRe et IS permet d'obtenir des résultats corrects, leur efficacité en terme de temps de calcul n'a pas semblé satisfaisante aux auteurs. Des améliorations ont donc été proposées dans une autre publication : « Efficient Identification of Overlapping Communities » [Baumes&al-2005-2] :

? L'algorithme RaRe a été remplacé par l'algorithme LA (Link Aggregate). Partant d'un classement des noeuds selon une métrique donnée (par exemple, le « PageRank ») et d'un ensemble de communautés vide, chaque noeud est ajouté à toute communauté dont il permet d'augmenter la densité. S'il n'a été ajouté à aucune communauté existante, une nouvelle communauté est créée.

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