Nouri, Khaled
(2019).
« Une nouvelle approche de détection de communautés dans les graphes bipartis » Mémoire.
Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en informatique.
Fichier(s) associé(s) à ce document :
Résumé
Beaucoup de données du monde réel peuvent être représentées par des graphes hétérogènes qui sont composés de plus d'un type de noeuds et de liens. À titre d'exemple de graphes hétérogènes, on trouve les graphes bipartis. Contrairement à la représentation standard de graphes où les noeuds et les liens sont de même type, les graphes bipartis sont caractérisés par la présence de deux types de nœuds reliés par un seul type de liens. L'analyse des graphes bipartis est l'un des nouveaux défis apparus en forage de données. Parmi les problématiques fondamentales étudiées dans ce domaine, on trouve la détection de communautés dont le but consiste à identifier des groupes de noeuds densément connectés entre eux et faiblement liés avec les noeuds d'autres groupes. Ces communautés ont souvent des caractéristiques similaires, ou des centres d'intérêt commun non connus à priori. La problématique de détection de communautés a été bien étudiée dans le cadre des graphes homogènes. Cependant, dans le contexte des graphes bipartis, cette problématique demeure une question de recherche ouverte. Cela est dû, d'une part, au fait que la structure topologique du graphe biparti est différente de celle du graphe ordinaire/ homogène, et d'autre part, l'absence d'une définition universellement acceptée quant à la notion de communauté dans les graphes bipartis. Un certain nombre d'approches a été proposé afin d'identifier des communautés dans les graphes bipartis. Toutefois, ces travaux existants souffrent d'au moins un des problèmes suivants : (1) la perte d'information à la suite de la transformation du graphe biparti en graphes homogènes (2) la sensibilité à la présence des nœuds non discriminants qui cachent la structure de communautés (3) la nécessité de spécifier manuellement le nombre de communautés ainsi que la restriction liée au fait que les deux types de noeuds du graphe biparti doivent avoir le même nombre de communautés. Afin de pallier les limites des approches existantes (mentionnées ci-dessus), nous présentons dans le cadre de ce mémoire, une nouvelle approche de détection de communautés dans les graphes bipartis. L'approche proposée se base sur une stratégie de détection de communautés qui relate la pertinence des noeuds combinée à une heuristique d'optimisation de la modularité bipartie afin d'identifier les structures de communautés finales. L'efficacité de l'approche proposée est comparée à d'autres méthodes récemment présentées sur des réseaux autant réels que synthétiques. Les résultats de cette comparaison montrent que notre approche offre une performance meilleure et parfois compétitive par rapport aux autres approches.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : Graphes bipartis, Détection de communautés, 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: |
Graphes bipartis / Détection de communautés |
| Unité d'appartenance: |
Faculté des sciences > Département d'informatique |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
31 juill. 2019 07:28 |
| Dernière modification: |
31 juill. 2019 07:28 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/12673 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
