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
| 
