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

Boutemine, Oualid (2016). « Une nouvelle approche de détection de communautés dans les réseaux multidimensionnels » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (10MB)

Résumé

L'analyse des graphes complexes, aussi appelés réseaux multidimensionnels ou réseaux multiplex, est l'un des nouveaux défis apparus en forage de données. Contrairement à la représentation classique de graphes où deux nœuds sont reliés par le biais d'une simple liaison, deux nœuds dans un réseau multidimensionnel se connectent par un ou plusieurs liens décrivant chacun une interaction spécifique dans une dimension particulière. Une des problématiques fondamentales étudiées dans ce domaine est la détection de communautés. Le but est de découvrir les sous-ensembles de nœuds densément connectés ou fortement interactifs, souvent, associés à des caractéristiques organisationnelles et fonctionnelles non connues à priori. Bien qu'elle ait fait l'objet de nombreuses études dans le contexte unidimensionnel, la détection de communautés dans les réseaux multidimensionnels demeure une question de recherche ouverte. C'est d'une part en raison des complexités inhérentes à ce type de réseaux et d'autre part, la conséquence de l'absence d'une définition universellement reconnue pour le concept de communauté multidimensionnelle. En dépit du nombre croissant de travaux abordant cette problématique, certains aspects demeurent peu ou pas abordés dans la littérature. En effet, les approches existantes souffrent d'au moins un des problèmes suivants : (1) La difficulté de fixer des valeurs propres aux paramètres d'entrée, (2) la sensibilité aux dimensions non pertinentes, et (3) l'incapacité de découvrir les sous-espaces de dimensions pertinentes associés aux communautés détectées. Afin de pallier les limites des approches existantes, nous présentons dans le cadre de ce mémoire une nouvelle approche de détection de communautés dans les réseaux multidimensionnels. Axée sur le principe de propagation d'étiquettes, l'approche développée vise l'identification automatique des structures denses dans les différents sous-espaces de dimensions, de même que leurs dimensions pertinentes via la maximisation d'une nouvelle fonction objective. L'efficacité de l'approche proposée est comparée à d'autres méthodes récentes par le biais d'une étude empirique détaillée sur différents réseaux synthétiques et réels. Les résultats obtenus démontrent la capacité de notre approche à identifier les communautés qui existent même dans des sous-espaces de faibles dimensions. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Détection de communautés, Réseaux multidimensionnels, Clustering.

Type: Mémoire accepté
Informations complémentaires: Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse: Bouguessa, Mohamed
Mots-clés ou Sujets: Réseaux multidimensionnels / Détection de communautés / Systèmes complexes / Exploration de données (Informatique) / Théorie des graphes
Unité d'appartenance: Faculté des sciences > Département d'informatique
Déposé par: Service des bibliothèques
Date de dépôt: 27 juill. 2016 14:44
Dernière modification: 27 juill. 2016 14:44
Adresse URL : http://archipel.uqam.ca/id/eprint/8714

Statistiques

Voir les statistiques sur cinq ans...