Une nouvelle approche de détection de communautés dans les réseaux sociaux

Talbi, Mohamed (2013). Une nouvelle approche de détection de communautés dans les réseaux sociaux. Mémoire. Gatineau, Université du Québec en Outaouais, Département d'informatique et d'ingénierie, 65 p.

Prévisualisation

PDF Télécharger (3MB) | Prévisualisation

Résumé

Un réseau social comme Facebook ou Twitter est un ensemble d'acteurs sociaux, tels des individus ou des organisations, reliés entre eux par des connexions représentant des interactions sociales. Il décrit une structure sociale dynamique par un ensemble de sommets et d'arêtes. L'analyse des réseaux sociaux, fondée principalement sur la théorie des graphes et l'analyse sociologique, vise à étudier diverses facettes de ces réseaux dont les principales sont: la détection de communautés, l'identification d'acteurs influents ainsi que l'étude et la prédiction de l'évolution des réseaux.
La détection de communautés consiste à former des groupes (disjoints ou chevauchants) de sorte que les nœuds au sein d'un même groupe soient connectés d'une manière dense. Dans le cas particulier de communautés disjointes, cela signifie aussi que les liens entre groupes sont faibles.
Dans le cadre de ce mémoire de maîtrise, nous présentons une nouvelle méthode de détection de communautés qui ne nécessite pas la connaissance apriori du nombre de communautés et vise à réduire considérablement le nombre d'itérations à effectuer sur un réseau initial en éliminant plusieurs liens (au lieu d'un seul lien) inter-communautés au cours d'une même itération. La méthode comporte deux phases et exploite la covariance des liens entre les nœuds et l'inertie inter-classes pour identifier les arcs à éliminer. Les communautés sont identifiées par maximisation de la modularité.
Une analyse empirique de notre approche et de quatre autres méthodes connues dans la littérature montre l'efficacité de notre approche à détecter des communautés même dans des graphes complexes où les groupes ne sont pas aisément identifiables. Les tests ont été menés sur des réseaux tant réels que synthétiques de diverses tailles et configurations.

Type de document:	Thèse (Mémoire)
Directeur de mémoire/thèse:	Missaoui, Rokia
Informations complémentaires:	Comprend des réf. bibliogr. : p. 62-65.
Mots-clés libres:	Exploration de données; Réseautage personnel; Réseaux sociaux; Détection de communautés; Informatique
Départements et école, unités de recherche et services:	Informatique et ingénierie
Date de dépôt:	27 sept. 2013 12:18
Dernière modification:	23 oct. 2015 13:12
URI:	https://di.uqo.ca/id/eprint/635

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt