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

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é

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 / IS²	[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é

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

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

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