WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

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

Positionnement des particules à l'état 3

Appropriation
de la particule
noire

Appropriation
de la particule
blanche

Valeurs de potentiel
des particules

 

Noeuds

État 3

Noeuds

État

3

Particules

 

État 3

 
 
 

App.

App.

Pot.

 
 

1

0.68

1

0.32

Noire

0.752

 

2

0.763

2

0.237

Blanc.

0.752

 

3

0.237

3

0.763

 
 

4

0.32

4

0.68

 

5

0.5

5

0.5

 

4 5

Figure 2.12e : État 3 illustration de la méthode de Fabricio Breve et al.

? Aux états 2 et 3, les particules commencent à faire évoluer leurs valeurs d'appropriation sur les noeuds de leur communauté respective : l'aléa amène la particule blanche à visiter le noeud 3 qui constitue une zone de recouvrement entre les deux communautés.

Positionnement des particules à l'état 4

Appropriation
de la particule
noire

Appropriation
de la particule
blanche

Valeurs de potentiel
des particules

1 2

Noeuds

État 4

Noeuds

État 4

Particules

 

État 4

 
 

App.

 

App.

Pot.

3

1

0.68

1

0.32

Noire

0.559

 

2

0.763

2

0.237

Blanc.

0.958

3

0.538

3

0.462

 
 
 

4

0.019

4

0.981

 

5

0.5

5

0.5

 

Figure 2.12f : État 4 - illustration de la méthode de Fabricio Breve et al.

1 2

3

4 5

? À l'état 4, la particule noire tente de s'aventurer sur le noeud 3 qui a, pour le moment, une forte valeur d'appropriation pour la particule blanche : cette valeur d'appropriation blanche empêche la particule noire de s'aventurer « physiquement » sur le noeud pour le moment, elle reste donc sur le noeud 2, son noeud de départ. La valeur d'appropriation de la particule noire sur le noeud 3 augmente au prix d'une diminution de son potentiel : cela peut être vu comme la force perdue par la particule noire dans son combat contre la particule blanche pour la possession du noeud 3.

Positionnement des particules à l'état 5

Appropriation
de la particule
noire

Appropriation
de la particule
blanche

Valeurs de potentiel
des particules

 

Noeuds

État 5

Noeuds

État 5

Particules

 

État 5

 

App.

 

App.

Pot.

 

1

0.904

1

0.096

Noire

0.869

1 2

2

0.763

2

0.237

Blanc.

0.891

3

0.538

3

0.462

 
 

4

0.019

4

0.981

3

5

0.117

5

0.883

 
 
 

4 5

Figure 2.12g : État 5 - illustration de la méthode de Fabricio Breve et al.

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

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

? À l'état 5, la particule blanche visite pour la première fois le noeud 5. À cette étape, les forts potentiels font que les valeurs d'appropriation peuvent évoluer très vite. Les communautés commencent déjà à se dessiner, comme le montrent la forte valeur d'appropriation de la particule noire sur les noeuds 1 et 2 et celle de la particule blanche sur les noeuds 4 et 5. Enfin, la valeur d'appropriation des deux particules sur le noeud 3 (aux alentours de 0.5) signale bien que ce noeud participe à un recouvrement entre les deux communautés.

Chaque particule a à la fois exploré un territoire pour se l'approprier et défendu des positions acquises. La méthode est séduisante, elle peut effectivement apparaître comme la mise en oeuvre d'un modèle intuitivement semblable avec celui du monde animal. Malgré tout il ne faut pas oublier que de nombreux paramètres comme Äv et Äñ sont à fixer préalablement pour la faire fonctionner et que la méthode requiert également le choix du nombre de communautés à créer. De plus, chaque communauté garde le plus souvent une participation (même si elle est infime) sur chaque noeud.

2.3.4 Méthodes modifiées pour permettre le recouvrement

Avec la prise de conscience que le recouvrement est généralement nécessaire pour coller à une réalité, les auteurs de méthodes modifient des méthodes existantes qui ne permettent pas le recouvrement afin de permettre le recouvrement.

Algorithme C.O.N.G.A. modifié

Un exemple intéressant est la méthode que Steve Gregory présente, dans « An Algorithm to Find Overlapping Community Structure in Networks » [Gregory-2010]. Il s'appuie sur les travaux menés par Newman et Girvan et l'algorithme C.O.N.G.A. (Cluster-Overlap Newman Girvan Algorithm) [Newman&al-2004-3]. Cet algorithme est basé sur la notion de mesure de centralité (betweeness centrality measure).

L'algorithme initialement proposé par Girvan et Newman consistait à retirer les arêtes dont la centralité est la plus élevée jusqu'à séparer le graphe en un certain nombre d'ensembles de noeuds disjoints. Cet algorithme n'autorisait donc pas les recouvrements entre communautés. L'idée de Steve Gregory est d'ajouter, en plus de la suppression d'une arête, la possibilité de réaliser une copie (virtuelle) d'un noeud du graphe en introduisant une arête virtuelle entre le noeud original et sa copie. De cette façon, un noeud pourra faire partie d'une ou plusieurs communautés distinctes.

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

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

L'algorithme CONGA est le suivant (où cB(v) représente la centralité du noeud v) :

TANT QUE il reste des arêtes faire

Trouver l'ensemble V des noeuds v tels que cB(v) > max (cB(e))

SI V n'est pas vide alors

Rechercher le noeud de V dont la meilleure scission a la plus grande centralité

Réaliser une copie du noeud trouvé selon sa meilleure scission

SINON

Supprimer l'arête de centralité maximale

FIN SI

Mettre à jour les valeurs de centralité de toutes les arêtes et noeuds du graphe

FIN TANT QUE

Figure 2.13 : Algorithme CONGA pour calculer la centralité de toutes les arêtes et noeuds du graphe.

Il existe généralement plusieurs façons d'introduire l'arête virtuelle. La solution retenue par Newman et Girvan [Newman&al-2004-3] est celle qui permet de maximiser la centralité de l'arête virtuelle introduite (voir figure 2.14 où, partant de la configuration de départ, on retiendra la configuration A). On parle de meilleure scission d'un noeud.

 
 
 
 

Graphe de départ

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Proposition A

 
 

Proposition B

 
 
 

Proposition C

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

B

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

2 A

 
 
 
 
 

D

6 6

2

6 6

C

r

B

D

B

6 6

ABD

D

B

D

6

6

2

6 6

2

6 6

E

Figure 2.14 : Insertion d'une arête virtuelle pour rechercher la proposition créant la plus haute valeur de

centralité.

2

6

2

4

2

2

ABC 8 ADE

ABE 4 ADC

6

ACE

6 6

C

E

C

E

C

L'algorithme a permis d'obtenir de bons résultats sur des cas tests standards. Toutefois, son temps de calcul est trop élevé pour une application sur des graphes très larges : 30411 secondes (plus de 8 heures) ont été nécessaires pour partitionner un graphe contenant seulement 3982 noeuds et 6803 arêtes (Pentium 4, 2.4 GHz).

Overlapping Stochastic Block Models modifié

Dans ces méthodes issues des méthodes de création de communautés sans recouvrement, une dernière méthode mérite notre attention. Pierre Latouche, Etienne Birmelé et Christophe Ambroise présentent, dans « Overlapping Stochastic Block Models with

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

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

Application to the French Political Blogosphere » [Latouche&al-2010], une extension de la méthode « Stochastic Block Models » autorisant les recouvrements. La méthode proposée recherche des classes dans le graphe : plus générale que la notion de communauté, une classe peut être une communauté mais peut également décrire des types très variés de connexion entre noeuds (présence de configurations en étoiles dans le graphe par exemple).

Dans la suite, on note X la matrice d'adjacence du graphe dirigé considéré. Chaque élément de la matrice noté Xij représente la présence ou l'absence d'une liaison de i à j. Partant d'un nombre de classes q fixé, l'idée est d'associer à chaque noeud un vecteur de q valeurs aléatoires (0 ou 1) Zi pour le noeud i dont chacun des q éléments suit une loi de Bernoulli.

On aura :

? Zi[c]=1 si le noeud i appartient à la communauté c, ? Zi[c]=0 sinon.

Plusieurs composantes du vecteur Zi pouvant être égales à 1, cette méthode autorise bien le recouvrement entre les différentes classes.

Connaissant les vecteurs Zi et Zj, on peut exprimer la loi conditionnelle Xij|Zi, Zj c'est-à-dire la probabilité qu'une liaison entre i et j existe (Xij=1) selon les valeurs prises par Zi et Zj c'est-à-dire selon l'appartenance des noeuds i et j à une communauté donnée.

Les auteurs proposent un algorithme d'optimisation basé sur la maximisation de la log-vraisemblance des données observées. L'objectif est donc de trouver le jeu de paramètres qui expliquent au mieux la présence ou l'absence d'arêtes (connexions) dans le réseau. Cette log-vraisemblance n'est pas calculable et les auteurs ont recours à une approximation variationnelle. L'algorithme proposé permet d'estimer à la fois les paramètres ainsi que les vecteurs Zi, c'est à dire les classes auxquelles appartiennent les noeuds du réseau.

La méthode a pour avantage d'ouvrir de nouvelles perspectives. La prise en compte de plusieurs éléments servant à construire les communautés est sans aucun doute un axe de recherche pertinent dans les graphes de terrain. En effet, dans le monde réel, les noeuds présentent des caractéristiques supplémentaires qui ne sont pas toutes représentées par le graphe. Ces caractéristiques peuvent donner lieu à la création de classes qui seront ensuite exploitées au mieux dans la création des communautés. Cette méthode reste cependant une proposition où le nombre de communautés doit être pré-prédéterminé.

2.4. Les méthodes de validation des communautés 74

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

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie