|
| Titre : |
Détection de Communauté dans Les Réseaux Sociaux |
| Type de document : |
texte imprimé |
| Auteurs : |
Belarbi,Ahmed Karim, Auteur ; Toumi,Lyazid, Directeur de thèse |
| Editeur : |
Setif:UFA |
| Année de publication : |
2019 |
| Importance : |
1 vol (86 f .) |
| Format : |
29 cm |
| Langues : |
Français (fre) |
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Détection de communautés
Réseaux sociaux |
| Index. décimale : |
004 - Informatique |
| Résumé : |
La capacité d’analyser les grands réseaux pour détecter les sous-ensembles de sommets plus densément connectés que d’autres, peut nous aider à comprendre et à visualiser la structure de ces réseaux. Les sous-ensembles appelé communautés.
La détection des communautés est appliquée dans des déférents domaines diversifiés tels que la sociologie, l’informatique, l’ingénierie et la biologie.
De fait, il s’agit de déterminer des classes dans un graphe. De nombreuses approches ont été proposées pour découvrir les structures de communautés dans les réseaux. Ces approches sont pour la plupart dédiées pour détecter les communautés disjointes. En biologie, où nous analysons les réseaux d’interactions protéine-protéine pour, entre autres, prédire leurs fonctions, nombreuses sont celles qui ont plusieurs fonctions et dans ce cas il est raisonnable de construire non pas une partition, mais un recouvrement, c’est à dire un système de classes chevauchantes. Il en est de même dans les réseaux sociaux, où les individus peuvent appartenir à plusieurs groupes.
On s'intéresse sur les méthodes de construction d’une partition des sommets du graphe qui maximisent un certain critère. Parmi les nombreux critères qui évaluent la qualité d’une partition, nous ne faisons ici référence qu’à la notion de modularité introduite par Newman. Malheureusement, son optimisation sur l’ensemble de toutes les partitions des sommets d’un graphe est un problème NP-difficile ; il en est évidemment de même pour les recouvrements. Il faut donc utiliser des méthodes heuristiques, dès lors que les graphes étudiés sont de grande taille. Dans ce mémoire, nous proposons deux méthodes approchées, l’une pour les partitions, ce qui permet d’optimiser la modularité (VOS Clustering) basée sur l'algorithme de Louvain, qui est actuellement le meilleur algorithme en termes de complexité, d’efficacité pour calculer des communautés sur de très grands graphes. L’autre pour les recouvrements, Elle est basée sur la première approche pour le nombre de communautés défini pour détecter les communautés chevauchantes, c’est l’algorithme FCM (Fuzzy C-Means).
Nous avons mis en place une évaluation de nos méthodes, après avoir les testés sur des différents benchmarks de graphes réels. Et nous avons présenté les résultats qui sont jugés satisfaisants après les comparés à ceux de la littérature. |
| Note de contenu : |
Sommaire
Dédicaces…………………………………………………………………………..ii
Remerciements………………………………………………………………..…..iii
Résumé……………………………………………..……………………………...iv
Table des matières…………………………………………………………….…..vi
Table de figures……………………………………………………………….…...x
Introduction Générale………………………….…………..……...………….…..13
1. Contexte générale……………………………………………………….13
2. Problématique et objectif de l’étude…………………………………….14
3. Contribution……………………………………………………………..14
4. Organisation du mémoire……………………………………...….……..14
Chapitre 1 : Notations et définitions
1.1 Introduction…………………….……………………………………..….…….……17
1.2 Réseau social………………….….………..…………………………….……...……17
1.3 Modélisation par les graphes………………………………………..…..…….…….18
1.4 Concepts…………….…………..……………………………………….…......….….19
1.4.1 Notion relative au graphe……………………..……………………….……...….19
1.5 Mesures de centralités……………………………………………...…..….…………23
1.5.1 Degré de centralité…………….....…………………………………...………....23
1.5.2 Centralité intermédiarité………………………..……………………....……….24
1.6 Modularité………………………………………………………………..…..………24
1.7 Graphe de terrain……………………………………………………….…..……….26
1.8 Communauté…………………………………………………………….……..…….26
1.9 Détection de communautés……………..……………………………………….…..27
vii
1.10 Analyse des réseaux sociaux……………………………………………………….28
1.11 Intérêt de la détection de communautés et ses applications……………….…….29
1.12 Conclusion…………………………...………………………………….…………..30
Chapitre 2 : Etat de l'art
2.1 Introduction………………………………………………………….………….32
2.2 Les approches de détection de communauté……………………………………32
2.2.1 Les approches statistiques sans recouvrements……………….…………32
2.2.1.1 Les approches hiérarchiques………………………………..……….33
2.2.1.1.1 Approche Hiérarchique Ascendantes…………….………34
2.2.1.1.2 Approche Hiérarchique Descendantes…….………..…….37
2.2.1.2 Partitionnement non hiérarchique…………………………..………41
2.2.1.2.1 Centre mobiles……………………………………..………41
2.2.1.2.2 Nuées dynamiques………………………………….……..42
2.2.1.3 Approches utilisant des marches aléatoires………………….……..42
2.2.1.4 Approches spectrales…………………………………………..…...44
2.2.2 Les approches statistiques avec recouvrement…………….………..…45
2.2.2.1 Approches basées sur des cliques………………………………..…46
2.2.2.2 Approches basé sur la propagation de labels………………….…....48
2.2.2.3 Approches basées sur des graines………………………….…….....51
2.3 Les approches dynamiques………………………………………………..52
2.3.1 Approches par détections statiques successives……………………….54
2.3.2 Les approches par détections statiques informées successives……….56
2.4 Conclusion…………………………………………………………..……..59
viii
Chapitre 3 : Contribution Et Algorithmes Etudiés
3.1 Introduction………………………………………………………………….61
3.2 Détection communautés avec la méthode VOS Clustering……………….61
3.2.1 Méthode de Louvain…………………………………………………61
3.2.1.1 Avantage……………………………………………………………..61
3.2.1.2 Inconvénient…………………………………………………….…...62
3.2.1.3 Exemple de détection de communautés pour des réseaux sociaux…...62
3.2.2 Vos Clustering…………………………………………………..……..63
3.2.2.1 Avantage……………………………………………………..………63
3.2.2.2 inconvénients………………………………………………..……….64
3.3 Détection les recouvrements avec la méthode de Fuzzy C-means……….…64
3.3.1 Avantages………………………………………………………………..…..65
3.3.2 Inconvénients……………………………………………………………..…65
3.4 Contribution…………………………………………………………………..65
3.4.1 Distance et métriques……………………………………………..………...66
3.4.1.1 Notion de distance………………………………………….………..66
3.4.1.2 Quelques types de distance………………………………….……….66
3.4.1.3 Similarité…………………………………………………….………68
3.5 Conclusion………………………………………………………………..……69
Chapitre 4 : Évaluation et Expérimentation.
4.1 Introduction…………………………………………………………………...71
4.2 Les langages utilisés et les outils d'implémentations………………………..71
4.2.1 Langage Python…………………………………………………………….71
4.2.2 PyCharm……………………………………………………………………71
4.3 Les Benchmarks de Test……………………………………………………...72
ix
4.3.1 Benchmark du Club de Karaté Zachary………………………………….72
4.3.2 Benchmark d’Albert Barabasi Model…………………………………….72
4.4 Format du fichier……………………………………………………………..72
4.5 Interfaces de notre application de détection de communauté…………..…74
4.5.1 Interface d’accueil………………………………………………………….74
4.5.2 Principe de fonctionnement de l’application……………………………..75
4.5.2.1 Détection de communautés partitionnées…………………………...76
4.5.2.2 Détection et analyse de communautés recouvrantes………………...81
4.6 Conclusion……………………………………………………………………..84
Conclusion générale………………………………………………………………85
Bibliographie……………………………………………………………………...86 |
| Côte titre : |
MAI/0295 |
| En ligne : |
https://drive.google.com/file/d/1h8tFrJ5pOSHjoIpKRj3dNDcit8Ql2XGD/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
Détection de Communauté dans Les Réseaux Sociaux [texte imprimé] / Belarbi,Ahmed Karim, Auteur ; Toumi,Lyazid, Directeur de thèse . - [S.l.] : Setif:UFA, 2019 . - 1 vol (86 f .) ; 29 cm. Langues : Français ( fre)
| Catégories : |
Thèses & Mémoires:Informatique
|
| Mots-clés : |
Détection de communautés
Réseaux sociaux |
| Index. décimale : |
004 - Informatique |
| Résumé : |
La capacité d’analyser les grands réseaux pour détecter les sous-ensembles de sommets plus densément connectés que d’autres, peut nous aider à comprendre et à visualiser la structure de ces réseaux. Les sous-ensembles appelé communautés.
La détection des communautés est appliquée dans des déférents domaines diversifiés tels que la sociologie, l’informatique, l’ingénierie et la biologie.
De fait, il s’agit de déterminer des classes dans un graphe. De nombreuses approches ont été proposées pour découvrir les structures de communautés dans les réseaux. Ces approches sont pour la plupart dédiées pour détecter les communautés disjointes. En biologie, où nous analysons les réseaux d’interactions protéine-protéine pour, entre autres, prédire leurs fonctions, nombreuses sont celles qui ont plusieurs fonctions et dans ce cas il est raisonnable de construire non pas une partition, mais un recouvrement, c’est à dire un système de classes chevauchantes. Il en est de même dans les réseaux sociaux, où les individus peuvent appartenir à plusieurs groupes.
On s'intéresse sur les méthodes de construction d’une partition des sommets du graphe qui maximisent un certain critère. Parmi les nombreux critères qui évaluent la qualité d’une partition, nous ne faisons ici référence qu’à la notion de modularité introduite par Newman. Malheureusement, son optimisation sur l’ensemble de toutes les partitions des sommets d’un graphe est un problème NP-difficile ; il en est évidemment de même pour les recouvrements. Il faut donc utiliser des méthodes heuristiques, dès lors que les graphes étudiés sont de grande taille. Dans ce mémoire, nous proposons deux méthodes approchées, l’une pour les partitions, ce qui permet d’optimiser la modularité (VOS Clustering) basée sur l'algorithme de Louvain, qui est actuellement le meilleur algorithme en termes de complexité, d’efficacité pour calculer des communautés sur de très grands graphes. L’autre pour les recouvrements, Elle est basée sur la première approche pour le nombre de communautés défini pour détecter les communautés chevauchantes, c’est l’algorithme FCM (Fuzzy C-Means).
Nous avons mis en place une évaluation de nos méthodes, après avoir les testés sur des différents benchmarks de graphes réels. Et nous avons présenté les résultats qui sont jugés satisfaisants après les comparés à ceux de la littérature. |
| Note de contenu : |
Sommaire
Dédicaces…………………………………………………………………………..ii
Remerciements………………………………………………………………..…..iii
Résumé……………………………………………..……………………………...iv
Table des matières…………………………………………………………….…..vi
Table de figures……………………………………………………………….…...x
Introduction Générale………………………….…………..……...………….…..13
1. Contexte générale……………………………………………………….13
2. Problématique et objectif de l’étude…………………………………….14
3. Contribution……………………………………………………………..14
4. Organisation du mémoire……………………………………...….……..14
Chapitre 1 : Notations et définitions
1.1 Introduction…………………….……………………………………..….…….……17
1.2 Réseau social………………….….………..…………………………….……...……17
1.3 Modélisation par les graphes………………………………………..…..…….…….18
1.4 Concepts…………….…………..……………………………………….…......….….19
1.4.1 Notion relative au graphe……………………..……………………….……...….19
1.5 Mesures de centralités……………………………………………...…..….…………23
1.5.1 Degré de centralité…………….....…………………………………...………....23
1.5.2 Centralité intermédiarité………………………..……………………....……….24
1.6 Modularité………………………………………………………………..…..………24
1.7 Graphe de terrain……………………………………………………….…..……….26
1.8 Communauté…………………………………………………………….……..…….26
1.9 Détection de communautés……………..……………………………………….…..27
vii
1.10 Analyse des réseaux sociaux……………………………………………………….28
1.11 Intérêt de la détection de communautés et ses applications……………….…….29
1.12 Conclusion…………………………...………………………………….…………..30
Chapitre 2 : Etat de l'art
2.1 Introduction………………………………………………………….………….32
2.2 Les approches de détection de communauté……………………………………32
2.2.1 Les approches statistiques sans recouvrements……………….…………32
2.2.1.1 Les approches hiérarchiques………………………………..……….33
2.2.1.1.1 Approche Hiérarchique Ascendantes…………….………34
2.2.1.1.2 Approche Hiérarchique Descendantes…….………..…….37
2.2.1.2 Partitionnement non hiérarchique…………………………..………41
2.2.1.2.1 Centre mobiles……………………………………..………41
2.2.1.2.2 Nuées dynamiques………………………………….……..42
2.2.1.3 Approches utilisant des marches aléatoires………………….……..42
2.2.1.4 Approches spectrales…………………………………………..…...44
2.2.2 Les approches statistiques avec recouvrement…………….………..…45
2.2.2.1 Approches basées sur des cliques………………………………..…46
2.2.2.2 Approches basé sur la propagation de labels………………….…....48
2.2.2.3 Approches basées sur des graines………………………….…….....51
2.3 Les approches dynamiques………………………………………………..52
2.3.1 Approches par détections statiques successives……………………….54
2.3.2 Les approches par détections statiques informées successives……….56
2.4 Conclusion…………………………………………………………..……..59
viii
Chapitre 3 : Contribution Et Algorithmes Etudiés
3.1 Introduction………………………………………………………………….61
3.2 Détection communautés avec la méthode VOS Clustering……………….61
3.2.1 Méthode de Louvain…………………………………………………61
3.2.1.1 Avantage……………………………………………………………..61
3.2.1.2 Inconvénient…………………………………………………….…...62
3.2.1.3 Exemple de détection de communautés pour des réseaux sociaux…...62
3.2.2 Vos Clustering…………………………………………………..……..63
3.2.2.1 Avantage……………………………………………………..………63
3.2.2.2 inconvénients………………………………………………..……….64
3.3 Détection les recouvrements avec la méthode de Fuzzy C-means……….…64
3.3.1 Avantages………………………………………………………………..…..65
3.3.2 Inconvénients……………………………………………………………..…65
3.4 Contribution…………………………………………………………………..65
3.4.1 Distance et métriques……………………………………………..………...66
3.4.1.1 Notion de distance………………………………………….………..66
3.4.1.2 Quelques types de distance………………………………….……….66
3.4.1.3 Similarité…………………………………………………….………68
3.5 Conclusion………………………………………………………………..……69
Chapitre 4 : Évaluation et Expérimentation.
4.1 Introduction…………………………………………………………………...71
4.2 Les langages utilisés et les outils d'implémentations………………………..71
4.2.1 Langage Python…………………………………………………………….71
4.2.2 PyCharm……………………………………………………………………71
4.3 Les Benchmarks de Test……………………………………………………...72
ix
4.3.1 Benchmark du Club de Karaté Zachary………………………………….72
4.3.2 Benchmark d’Albert Barabasi Model…………………………………….72
4.4 Format du fichier……………………………………………………………..72
4.5 Interfaces de notre application de détection de communauté…………..…74
4.5.1 Interface d’accueil………………………………………………………….74
4.5.2 Principe de fonctionnement de l’application……………………………..75
4.5.2.1 Détection de communautés partitionnées…………………………...76
4.5.2.2 Détection et analyse de communautés recouvrantes………………...81
4.6 Conclusion……………………………………………………………………..84
Conclusion générale………………………………………………………………85
Bibliographie……………………………………………………………………...86 |
| Côte titre : |
MAI/0295 |
| En ligne : |
https://drive.google.com/file/d/1h8tFrJ5pOSHjoIpKRj3dNDcit8Ql2XGD/view?usp=shari [...] |
| Format de la ressource électronique : |
pdf |
|
Ajouter le résultat dans votre panier Affiner la recherche
