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

? 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

(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 :

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é :

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 :

Ä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

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie