Chapitre 2. Les algorithmes de création de
communautés
? L'algorithme IS a également été
remplacé par l'algorithme IS2, plus efficace car restreignant
la recherche des points à ajouter, aux seuls noeuds adjacents à
la communauté actuelle : sur les grands graphes, cela permet de
réduire considérablement le nombre de possibilités
à explorer.
La combinaison des algorithmes LA et IS2 ne
nécessite pas de fixer le nombre de communautés à
l'avance. Le nombre de communautés proposé une fois le traitement
effectué, est fonction du choix des critères d'extraction des
noeuds importants.
Détection de communautés et fusion des
communautés proches
En 2010, Arnau Padrol-Sureda, Guillem Perarnau-Llobet, Julian
Pfeifle et Victor Munt'es-Mulero présentent l'algorithme OCA
(Overlapping Community Algorithm) permettant de détecter des
communautés avec recouvrement
[Padrol-Sureda&al-2010]. Cet algorithme se veut
particulièrement adapté aux très grands graphes. Il
s'appuie sur l'optimisation locale d'une fonction « objectif »
permettant d'évaluer la qualité d'une communauté.
Constitué d'une première phase dont le but est de fractionner
fortement le graphe, une seconde phase agrégera les communautés
trop proches.
Graphe
Représentation vectorielle du graphe
X
Y
Z
T
Figure 2.9 Exemple de graphe et représentation
vectorielle associée.
Afin de poser les bases théoriques de leur
méthode, les auteurs visualisent un graphe comme un ensemble de vecteurs
dans un espace de grande dimension (cf. figure 2.9).
Chaque noeud i du graphe est associé à
un vecteur vi et tout sous-graphe {i1,...,in} est
associé à la somme des vecteurs qui le composent. La règle
suivante est adoptée :
<vi,vk> = | vi || vk | cos(vi,vk) = c
Où (0 < c < 1) s'il existe une arête
reliant i à k, c = 0 sinon (angle droit entre vi et vk
si
i et k ne sont pas connectés).
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 62
Chapitre 2. Les algorithmes de création de
communautés
Comme on peut le voir sur la figure 2.9, y+z (y et z
sont connectés) est plus éloigné de 0 que x+t (x
et t ne sont pas connectés) : la première idée est donc de
choisir la norme euclidienne au carré comme fonction (9
à maximiser ((9(v) = longueur du vecteur v au
carré). Malheureusement, le maximum de cette fonction est atteint
lorsque le graphe est contenu dans une seule et même communauté :
en effet, comme le montre la figure 2.9, le vecteur de longueur la plus
élevée est le vecteur x+y+z+t. Cette fonction ne peut
donc pas être utilisée seule. En effet, si on la maximise toutes
les composantes connexes deviendront des communautés.
De façon à éviter ce problème, les
auteurs proposent de s'intéresser à l'impact du rajout ou de la
suppression d'un noeud sur l'augmentation ou la diminution de (9. Pour
cela, ils introduisent la notion de laplacien dirigé L. L peut
s'apparenter à une dérivée lorsqu'on parle de fonction :
ce laplacien permet d'évaluer dans quelles « directions » on
peut espérer obtenir une augmentation de la valeur de la fonction
(9. La valeur en v de L pour une fonction f
est définie par la formule :
Où u représente un voisin de v appartenant
à la communauté testée. La fonction indeg(x) retourne le
degré entrant du noeud x.
Les variations de L sur l'ensemble de la communauté en
ajoutant ou supprimant un noeud seront utilisées par l'algorithme OCA.
L'algorithme OCA est, en fait, une première phase de l'ensemble du
traitement, cette première phase recherchant les communautés
indépendamment les unes des autres. Il démarre d'une graine
positionnée aléatoirement dans le graphe. Le noeud permettant la
plus grande augmentation de L est ajouté à la communauté
et ce processus est répété jusqu'à ce que plus
aucune amélioration ne puisse être obtenue ; ceci, autant de fois
qu'il le faut pour former l'ensemble des communautés du graphe.
|
Tant que critère d'arrêt non
satisfait faire
Choisir un noeud (graine) aléatoirement dans le graphe --
(cette graine est le premier élément de la communauté
k)
Pour chaque Noeud de la composante connexe
faire
Si le Laplacien dirigé L augmente
alors
Ajouter ce noeud à la communauté k
Fin de si
Noeud suivant
Fin de tant que
Post-traitement des résultats : fusionner
les communautés proches les unes des autres de façon à
éviter des
communautés trop proches et à permettre le
recouvrement.
|
Figure 2.10 : Algorithme de la méthode d'Arnau
Padrol-Sureda, Guillem Perarnau-Llobet, Julian Pfeifle et Victor Munt'es-Mulero
[Padrol-Sureda&al-2010].
Le plus grand intérêt de cet algorithme est de
permettre le traitement de très grands graphes en un temps relativement
court : testé sur le graphe de Wikipedia (16 986 429
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 63
Chapitre 2. Les algorithmes de création de
communautés
(16 986 429 noeuds, 176 454 501 arêtes) sur lequel un
résultat a été obtenu en 3,25 heures seulement. OCA est,
de plus, fortement parallélisable.
Selon les auteurs, les résultats obtenus
nécessitent un post-traitement. En effet, selon la position des graines
dans le graphe, des communautés extrêmement proches sont
retournées. Ces communautés doivent alors être
fusionnées pour arriver au partitionnement final du graphe.
Méthode spectrale et Fuzzy C-mean
Création de communautés puis fusion
avec recouvrements
En 2007, dans un article nommé «
Identification of overlapping community structure in complex networks using
fuzzy c-means clustering », Shihua Zhang, Rui-Sheng Wang et Xiang-Sun
Zhang décrivent une méthode géométrique de
partitionnement d'un graphe [Zhang&al-2007]. Cette
méthode fait appel à une analyse spectrale du graphe puis
à l'algorithme fuzzy c-means.
Partant d'un majorant K du nombre de communautés,
l'algorithme permet d'établir un degré d'appartenance de chaque
noeud à une communauté : on note uik le
degré d'appartenance du noeud i à la communauté
k, on aura donc ?uik= 1 pour tout noeud i.
Comme beaucoup d'algorithmes de recherche de
communautés, celui qui est présenté dans ce document fait
appel à la notion de modularité introduite par Newman : les
auteurs ont introduit une version modifiée de la modularité
permettant de tenir compte des recouvrements.
Soit A la matrice d'adjacence du graphe et D
la matrice diagonale (ou matrice des degrés) telle que dii = ?j
Aij.
L'algorithme se décompose en trois phases qui sont : ?
Projection du graphe dans un espace euclidien
Une méthode spectrale permettant de projeter les noeuds
du graphe dans un espace euclidien de faible dimension est utilisée :
cette opération nécessite le calcul des K vecteurs
propres généralisés dominants du système Ax =
tDx.
? Partitionnement par fuzzy c-means
Une fois les noeuds du graphe projetés dans un espace
euclidien, l'algorithme fuzzy c-means est utilisé pour former des
communautés dans cet espace géométrique. Il utilise un
critère de minimisation des distances intra-communautés et de
maximisation des distances inter-communautés. Il calcule pour chaque
noeud, un certain niveau d'appartenance à chaque classe en minimisant
une fonction objective. Cet algorithme nécessite la connaissance
préalable du nombre de communautés et les génère en
utilisant un algorithme itératif minimisant une fonction.
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 64
Chapitre 2. Les algorithmes de création de
communautés
Les principales étapes de l'algorithme fuzzy c-means
introduit par Dunn en 1973 [Dunn-1973] sont :
1. la détermination arbitraire d'une matrice
d'appartenance ;
2. le calcul des centroïdes des classes ;
3. le réajustement de la matrice d'appartenance
suivant la position des centroïdes ;
4. le calcul du critère de minimisation et retour
à l'étape 2 s'il y a non convergence de critère.
L'algorithme fuzzy c-means utilise, ici, comme fonction «
objectif » la fonction définie par l'équation suivante :
Où uij est le degré d'appartenance de
xi dans la communauté j. cj est le centre du
jème ensemble, xi est le
ième point de données (dans notre cas, xi
sont les coordonnées du noeud i projeté dans
l'espace euclidien). m est un paramètre de la méthode
utilisé comme élément de réglage. Il permet selon
les auteurs de régler le niveau de « flou », ce que nous
pourrions traduire par la proportion de surfaces en recouvrement.
Afin d'identifier le nombre correct de communautés,
l'opération de partitionnement est réalisée pour tous les
k tels que 2 = k = K.
? Maximisation de la modularité
La fonction de modularité est évaluée
pour chacun des partitionnements réalisés : la valeur de k
maximisant la modularité et le partitionnement associés sont
alors retenus.
La méthode proposée est intéressante car
elle permet de visualiser le graphe dans un espace de petite dimension. De
plus, seule la connaissance d'un majorant du nombre de communautés est
nécessaire. En revanche, comme il est nécessaire de
résoudre de nombreux problèmes aux vecteurs propres pour parvenir
au résultat, l'utilisation de cet algorithme est rendue difficile sur
des graphes de grande taille malgré la performance des méthodes
numériques actuelles.
2.3.3 Les méthodes par déplacement
d'objets
Parmi les méthodes permettant la création de
communautés en recouvrement, figurent les méthodes par
déplacement d'objets. L'attribution d'un noeud à une ou plusieurs
communautés se fait soit en déplaçant le noeud entre les
communautés soit en déplaçant des agents
représentant une communauté d'un noeud à l'autre. Dans un
cas comme dans l'autre, à chaque
itération, on recalculera les coefficients
d'appartenance entre les communautés et les noeuds. Ces méthodes
sont toutes basées sur un nombre prédéterminé de
communautés à
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 65
Chapitre 2. Les algorithmes de création de
communautés
créer. Si certaines méthodes ont la
possibilité d'utiliser ce nombre comme un maximum, les algorithmes par
déplacement d'objets sont tous séparatistes.
Le déplacement des noeuds
En 2010, dans un article nommé « A
Game-Theoretic Framework to Identify Overlapping Communities in Social Networks
», Wei Chen, Zhenming Liu, Xiaorui Sun et Yajun Wang proposent
d'assimiler la formation des communautés à un jeu où
chaque noeud serait un agent égoïste cherchant à maximiser
sa propre « utilité » [Chen&al-2010].
Ainsi, à chaque itération, chaque noeud pourra quitter une
communauté et/ou en rejoindre une autre : un changement ne sera
accepté que s'il amène le noeud à maximiser son
utilité.
L'utilité d'un individu est traduite par deux termes :
un terme de « gain » tenant compte d'une modularité qui
représente la capacité de l'individu à renforcer la
communauté et un terme de « perte » qui est d'autant plus
grand que l'individu fait partie d'un grand nombre de communautés.
La notion de gain s'appuie sur une version enrichie de la
modularité telle qu'on peut la trouver chez Newman
[Newman-2006]. Les auteurs parlent de « Nash equilibra
» pour signifier que, dans le jeu de placement,
les noeuds sont en quelque sorte coopératifs. Ils ne jouent pas
les uns contre les autres mais les uns pour les autres, en équipe ou
encore dans une stratégie gagnant-gagnant.
Sous certaines conditions sur les fonctions « gain »
et « perte », il a été démontré que
l'algorithme proposé converge vers un équilibre local donc vers
une solution satisfaisante de partitionnement du graphe. La méthode
présente l'avantage de n'avoir à connaître qu'un majorant
du nombre de communautés.
L'accroissement des semences
L'accroissement des semences diffère fortement du
déplacement de noeuds. Le mouvement est ici donné par
l'accroissement de la taille de la communauté à partir de la
graine.
En 2010, dans un article nommé « Identifying
Community Structures in Networks with Seed Expansion », Fang Wei,
Weining Qian, Zhongchao Fei et Aoying Zhou décrivent une méthode
basée sur un processus d'expansion à partir d'un ensemble de
graines initialement réparties sur des sommets du graphe
[Vei&al-2010]. Les auteurs définissent la
méthode comme agrégative. Elle en a certains aspects. Pourtant
nous la classerons ici comme une méthode séparatiste. En effet,
le nombre de communautés est prédéterminé il y a
donc avant tout un partage du graphe en N communautés.
L'algorithme présente le comportement suivant :
à chaque itération, de nouveaux noeuds peuvent être
ajoutés à chaque communauté issue d'une graine. Dans
l'algorithme proposé, la probabilité de choisir un noeud libre
donné est inversement proportionnelle à son degré.
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 66
Chapitre 2. Les algorithmes de création de
communautés
Pour une communauté donnée, une fois toutes les
probabilités calculées, celles-ci sont classées par ordre
décroissant. Partant du noeud ayant la probabilité la plus
élevée, le changement de modularité induit par l'ajout de
ce noeud à la communauté est calculé : si l'ajout du noeud
mène à une augmentation de la modularité, le noeud est
ajouté à la communauté ; sinon, on répète le
processus sur le noeud suivant.
Le principal inconvénient de cette approche est encore
une fois de devoir fixer le nombre de communautés (le nombre initial de
graines) à priori. De plus, le choix de la position des graines,
primordial pour obtenir de bons résultats, n'est pas une tâche
facile, en particulier sur des très grands graphes.
Le déplacement de particules
Le déplacement de particules est le résultat
d'un paradigme où les noeuds représentent des espaces stables de
résidences et les liaisons, des éléments permettant
uniquement de se déplacer d'un noeud à un autre. Des particules
vont se « promener » en sautant de noeuds en noeuds, chaque
occupation d'un noeud par une particule lui permettant de recalculer
positivement son niveau de possession.
En se fondant à la fois sur les notions de «
ballade aléatoire », de niveaux d'appartenance et de
déplacements choisis, Fabricio Breve, Liang Zhao et Marcos Quiles ont
proposé en 2009, dans l'article « Uncovering Overlap Community
Structure in Complex Networks Using Particle Competition », une
nouvelle méthode [Breve&al-2010]. Cette
méthode permet de détecter les recouvrements entre
communautés dans un réseau complexe.
La méthodologie proposée s'appuie sur une
compétition entre un ensemble de c objets mobiles,
nommés particules {â1,...,âc} qui
évoluent dans le réseau en se déplaçant de noeud en
noeud. Chaque particule représente une communauté Ci
distincte. Le nombre de communautés créées est
égal au nombre de particules mises en oeuvre. L'appartenance d'un noeud
à une communauté est alors la résultante de la possession
d'un noeud par une particule. Si plusieurs particules se partagent le noeud
alors nous sommes en présence de zones de recouvrement.
À l'état initial, la méthode va
prédisposer les particules de façon aléatoire sur les
noeuds du graphe. Chacune des particules se voit attribuer un niveau de
propriété P égal sur l'ensemble des noeuds du graphe. Ce
niveau de propriété est équivalent au niveau
d'appartenance du noeud à une communauté.
À chaque étape de l'algorithme, les particules
pourront se déplacer soit de façon aléatoire vers un noeud
voisin soit de façon déterministe. Le choix du type de
déplacement est fixé par un coefficient K, choisi au
départ. Ensuite, de manière statistique, afin de respecter ce
coefficient, la particule choisit son type de déplacement. Les
particules peuvent se déplacer de deux façons dans le
réseau :
? mouvement aléatoire : la particule se déplace sur
un noeud adjacent avec une probabilité égale pour chacun des
noeuds visitables ;
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 67
Chapitre 2. Les algorithmes de création de
communautés
? mouvement déterministe : la particule se
déplace sur un noeud adjacent avec une probabilité
dépendant de son niveau de propriété sur chacun des noeuds
visitables. Dans ce cas-là, la particule a tendance à visiter des
noeuds où sa propriété est déjà forte par
rapport aux autres particules. Le niveau de propriété
exprimé par la particule est aussi le niveau d'appartenance du noeud
à une communauté, puisque chaque particule représente une
communauté.
Le mouvement déterministe permet aux particules de
garder la main sur les noeuds qui leur appartiennent tandis que le mouvement
aléatoire permet de visiter les noeuds participant au recouvrement avec
une autre communauté. Le coefficient K sert alors à
régler le niveau de « curiosité » de la particule
voyageuse.
La somme de l'ensemble des propriétés des
particules sur un noeud donné ne pouvant pas dépasser 100%, les
particules vont alors mener une compétition pour s'octroyer la
propriété des noeuds. Le niveau de propriété entre
les particules et les noeuds va alors s'ajuster au fur et à mesure des
itérations.
Chaque particule dispose en outre d'un potentiel indiquant sa
« force ». Ce potentiel permet à la particule de pouvoir
rivaliser ou non avec les autres particules : ainsi, si une particule n'est pas
assez forte, elle ne pourra pas s'aventurer dans une zone appartenant à
une particule plus forte qu'elle. La particule va perdre ou gagner du potentiel
(ou de sa « force ») au prorata du coût de son
déplacement. Si le noeud à éteindre au temps (t +1)
est un noeud sur lequel la particule a un fort niveau de
propriété sa force augmente et elle baissera dans le cas
contraire.
La particule Pj possède donc à
l'instant t un potentiel notée Pjù(t).
Ce potentiel correspond à la valeur de la « force » avec
laquelle la particule peut « s'affecter » un noeud. Cette valeur est
bornée par ùmin et ùmax tel que
ùmin = 0 et ùmax=1.
À chaque itération de la boucle de l'algorithme,
on se place ici dans le cas où le noeud i a été
choisi par la particule j au temps (t +1), les
propriétés et les potentiels sont mis à jour par les
formules ci-dessous :
? Calcul de la propriété :
Où viùk(t) est la
propriété de la particule k sur le noeud i au
temps t et ñjù le potentiel de la
particule j à un instant donné
? Calcul du potentiel :
Où Äv et
Äñ sont deux paramètres permettant de
contrôler la vitesse d'évolution des deux grandeurs
(propriété et potentiel).
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 68
Chapitre 2. Les algorithmes de création de
communautés
La méthode permet, après un certain nombre
d'exécutions de l'algorithme, de déterminer un degré
d'appartenance d'un noeud à une communauté : un noeud vi
aura un fort degré d'appartenance à la communauté
Ck si le degré de propriété de la particule
âk sur le noeud vi est fort. L'algorithme
permettant le calcul des valeurs de propriété et de potentiel
peut donc se lire ainsi :
|
POUR la particule J voulant aller en
noeud i faire
POUR K=1 à nombre de particules
faire
SI k différent de j
alors
La valeur de propriété de la particule K
sur le noeud i au temps t+1 est égale à la
valeur maximale entre la borne ùmin et sa valeur au
temps t moins le rapport du coefficient Äv multiplié par
la valeur du potentiel de la particule K sur le noeud j au
temps t sur le nombre de communauté moins 1.
SI NON (k=j)
La valeur de propriété de la particule J sur le
noeud i au temps t+1 est égale à sa valeur au temps
t + différence de propriété des autres
communautés entre le temps t et le temps t +1. Ceci
afin de s'assurer que la somme des coefficients de propriété de
chaque noeud est conservée toujours égale à 1.
FIN DE SI
FIN DE POUR k
Le potentiel au temps t+1 de la particule j sur
le noeud i est égal au potentiel au temps t + le
coefficient Äñ multiplié par la
propriété de la particule au temps t+1 sur le noeud
j moins le potentiel de la particule J au temps
t.
FIN DE POUR voulant aller en i
|
Figure 2.11 : Algorithme de la méthode de Fabricio
Breve, Liang Zhao et Marcos Quiles 2009.
Ces degrés d'appartenance permettent, en outre, de
définir un indice de recouvrement oi de telle sorte qu'un indice proche
de 0 indique que le noeud appartient avec certitude à une seule
communauté et un indice proche de 1 indique que le noeud appartient avec
certitude à deux communautés ou plus.
Un exemple d'exécution de l'algorithme sur un
réseau simple avec 5 noeuds et 2 particules est donné ci-dessous.
On a choisi Äv=0,4 et
Äñ=0,9.
|
Un graphe de 5 noeuds
|
|
2 particules (afin de créer 2
communautés) : une noire et
une blanche
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1
|
|
2
3
5
Figure 2.12a : Les éléments en
interaction pour illustrer la méthode de Fabricio Breve et
al.
2.3. Les différentes méthodes de recherche de
communautés avec recouvrement 69
Chapitre 2. Les algorithmes de création de
communautés
À chaque itération de l'algorithme, les particules
recalculent les différents niveaux d'appartenance et de polarité
:
|
Positionnement des particules à l'état
0
|
Appropriation
de la particule
noire
|
Appropriatio
n de
la
particule
blanche
|
Valeurs de potentiel
des particules
|
|
Noeuds
|
État 0
|
Noeuds
|
État 0
|
Particules
|
|
État 0
|
|
|
App.
|
|
App.
|
Pot.
|
|
|
1
|
0.5
|
1
|
0.5
|
Noire
|
0
|
|
2
|
0.5
|
2
|
0.5
|
Blanc.
|
0
|
|
3
|
0.5
|
3
|
0.5
|
|
|
|
4
|
0.5
|
4
|
0.5
|
|
5
|
0.5
|
5
|
0.5
|
|
|
|
4 5
Figure 2.12b : État 0 - illustration de la
méthode de Fabricio Breve et al.
? À l'état initial 0, les deux
particules sont placées aléatoirement sur le noeud 1 pour la
particule noire et sur le noeud 5 pour la particule blanche. Les potentiels
sont définis à ùmin soit à 0 et les
valeurs d'appropriation de manière équitable entre les noeuds et
les particules.
|
1 2
Positionnement des particules à l'état
1
|
appropriation
de la particule
noire
|
Appropriation
de la particule
blanche
|
Valeurs de potentiel
des particules
|
|
Noeuds
|
État 1
|
Noeuds
|
État 1
|
Particules
|
|
État 1
|
|
3
|
|
App.
|
|
App.
|
Pot.
|
|
|
1
|
0.5
|
1
|
0.5
|
Noire
|
0.45
|
|
2
|
0.5
|
2
|
0.5
|
Blanc.
|
0.45
|
|
3
|
0.5
|
3
|
0.5
|
|
|
|
4
|
0.5
|
4
|
0.5
|
|
5
|
0.5
|
5
|
0.5
|
|
4 5
Figure 2.12c : État 1- illustration de la
méthode de Fabricio Breve et al.
1 2
3
? À l'état 1, les deux
particules sont déplacées de manière probabiliste sur des
noeuds adjacents : les valeurs d'appropriation n'évoluent pas (car les
potentiels
sont nuls en début d'exécution) mais les potentiels
soit initialisés.
|
Positionnement des particules à l'état
2
|
Appropriation
de la particule
noire
|
Appropriation
de la particule
blanche
|
Valeurs de potentiel
des particules
|
|
Noeuds
|
État 2
|
Noeuds
|
|
État
2
|
Particules
|
|
État 2
|
|
|
|
App.
|
App.
|
Pot.
|
|
|
1
|
0.68
|
1
|
0.32
|
Noire
|
0.657
|
|
|
2
|
0.5
|
2
|
0.5
|
Blanc.
|
0.657
|
|
1 2
|
3
|
0.5
|
3
|
0.5
|
|
|
|
4
|
0.32
|
4
|
0.68
|
|
5
|
0.5
|
5
|
0.5
|
|
3
4 5
Figure 2.12d : État 2 illustration de la
méthode de Fabricio Breve et al.
2.3. Les différentes méthodes de recherche
de communautés avec recouvrement 70
| 
