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

2.5.2 Méthodes créant des communautés sans recouvrement

Méthodes

Ref

Famille

Graphe

Nb de communautés

Résumé

Min-cut

[Kernigha&al-

1970]

Algorithmes
séparatistes

orienté

non
orienté

prédéterminé

Basé sur le rapport du nombre de liaisons intercommunautaire sur le nombre intra-communautaire.

 

pondéré

non
pondéré

 

Partitionnement
par groupe de
voisinage

[Jain&al-1999]

Algorithmes
séparatistes

orienté

non
orienté

prédéterminé

Transformation des liaisons en système de localisation dans un espace euclidien, puis découpage par zones de fort voisinage.

 

pondéré

non
pondéré

Découpage de
dendrogramme

[Ward-1963]

Algorithmes
séparatistes

orienté

non
orienté

Choisi en fonction du critère
de qualité sélectionné
(centralité)

Création d'un dendrogramme, puis création de communautés (chaque sommet de l'arbre est un départ d'une communauté). Les communautés peuvent ensuite être couplées pour en diminuer le nombre.

 

pondéré

non
pondéré

 

Balade aléatoire

[Pons&al-2005]

Algorithmes
séparatistes

orienté

non
orienté

Choisi en fonction du critère
de qualité sélectionné
(modularité)

Algorithme qui représente le graphe comme un espace à parcourir. Plus la balade

est statistiquement probable, puis l'espace est potentiellement une
communauté.

pondéré

non
pondéré

Heuristic
procedure

[Newman-2004-

3]

Algorithmes de
scission

orienté

non
orienté

Déterminé par le nombre de
scissions.

Algorithme qui supprime des liaisons faibles de façon à transformer chaque composante connexe résultante en communauté. Les liaisons faibles sont par exemple des liaisons à forte centralité.

 

pondéré

non
pondéré

recherche de
zones de forte
modularité

[Rossia&al-2010]

Détection de zones

orienté

non
orienté

Déterminé par la valeur
minimale de la modularité

Algorithme qui détermine les zones denses comme des communautés. Cet

algorithme a la particularité de ne pas placer tous les noeuds dans une
communauté.

 

pondéré

non
pondéré

Tableau 2.1 : Méthodes créant des communautés sans recouvrement.

2.5. Synthèse 83

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

2.5.3 Méthodes créant des communautés avec recouvrement

Méthodes

Ref

Famille

Graphe

Nb de communautés

Résumé

C-finder

[Palla&al-2005]

Recherche de

forme :
Percolation de

clique

orienté

non orienté

Déterminé par le choix d'un
coefficient K

Algorithme qui recherche des formes identifiables. Un noeud peut ou pas appartenir à une ou plusieurs communautés. Les noeuds ne sont pas tous rattachés à une communauté. Cet algorithme est devenu un des plus utilisés. Particulièrement efficace dans les réseaux ou le degré maximal est limité, il est plus délicat à mettre en oeuvre dans de grands graphes de terrain ou le degré est très hétérogène.

pondéré

non pondéré

 
 

Enrichissement
de noyaux

[Shang&al-2007]

Méthode en X
phases

orienté

non orienté

Déterminé par le choix d'un
coefficient K (phase 1) et par
les règles de regroupement des
noyaux (phase 3)

Algorithme qui recherche des formes identifiables identiques au C-finder, puis qui regroupe les noyaux créés et les enrichit ensuite avec les noeuds excentrés. Une grande majorité des noeuds peuvent ainsi être dans une communauté.

pondéré

non pondéré

 
 

RaRe/IS et LA /

IS2

[Baumes&al-2005-1]

Méthode en X
phases

orienté

non orienté

Déterminé par la méthode de
création des noyaux (RaRe ou

LA)

Les noeuds présentant les PageRank les plus élevés sont supprimés de façon à

créer des composantes connexes. Ces composantes connexes sont les
communautés. Elles sont ensuite enrichies par le retour des noeuds qui sont en recouvrement.

pondéré

non pondéré

 
 

OCA

[Padrol-Sureda&al-

2010]

Méthode en X
phases

orienté

non orienté

Déterminé par le nombre de
graines au départ

Cet algorithme se veut avant tout un algorithme efficace et rapide. Il nécessite une phase de post-traitement qui va regrouper les communautés trop proches.

pondéré

non pondéré

 
 

Analyse
spectrale et
Fuzzy c-means

[Zhanag&al-2007]

Méthode en X
phases

orienté

non orienté

Majorant prédéterminé

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.

pondéré

non pondéré

 
 

Nash equilibra

[Chen&al-2010]

Déplacement
de noeuds

orienté

non orienté

Majorant prédéterminé

Un noeud se déplace d'une communauté à une autre en cherchant à maximiser son « utilité ». Un noeud utile augmente la modularité de la communauté qu'il rejoint.

pondéré

non pondéré

 
 

Seed expansion

[Vei&al-2010]

Déplacement
de graines

orienté

non orienté

Prédéterminé

Cet algorithme calcule la probabilité qu'un noeud appartienne à une

communauté de telle façon que plus son appartenance augmente la modularité plus sa probabilité d'appartenir à cette communauté est forte.

pondéré

non pondéré

 
 

Particle
Competition

[Breve&al-2010]

Déplacement
de particules

orienté

non orienté

Prédéterminé

L'algorithme déplace des particules de façon semi aléatoire à l'intérieur du graphe. Chaque particule représente une communauté. À chaque déplacement les noeuds rejoints par la particule lui appartiennent un peu plus.

pondéré

non pondéré

 
 

CONGA modifié

[Gregory-2010]

Méthode modifiée pour permettre le recouvrement

orienté

non orienté

Déterminé par le nombre de
scissions

Algorithme qui rajoute des liaisons virtuelles en « dédoublant » certains noeuds. Une fois la liaison portant la plus haute centralité trouvée, on peut la supprimer. Les composantes connexes créées sont alors des communautés, les noeuds dédoublés étant partagés par les communautés créées.

pondéré

non pondéré

 
 

Stochastic
Block Models
modifié

[Latouche&al-2010]

Méthode modifiée pour permettre le recouvrement

orienté

non orienté

Prédéterminé

L'objectif est donc de trouver le jeu de paramètres (á,W) qui expliquent, au mieux, la présence ou l'absence d'arêtes (connexions) dans le réseau.

pondéré

non pondéré

 
 

Tableau 2.2 : Méthodes créant des communautés avec recouvrement.

2.5. Synthèse 84

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

précédent sommaire suivant