University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Douadi, Asma |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Detection de communautes dans les reseaux dynamiques Type de document : texte imprimé Auteurs : Douadi, Asma, Auteur ; Kamel, Nadjet, Directeur de thèse Editeur : Setif:UFA Année de publication : 2018 Importance : 1 vol (51 f .) Format : 29 cm Langues : Français (fre) Langues originales : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Détection de communautés
Réseaux dynamiques
Réseaux temporels
Evolution des commnautésIndex. décimale : 004 Informatique Résumé : Résumé
Plusieurs études ont montré que les réseaux modélisant des phénomènes du monde réel sont caractérisés par des propriétés remarquables : ils sont organisés en fonction de la structure de la communauté et cette dernière évolue avec le temps. De nombreux chercheurs ont travaillé sur des méthodes permettant de dévoiler efficacement des sous-structures dans les réseaux, donnant naissance au domaine de la détection de communauté. Les réseaux dynamiques peuvent être utilisés pour modéliser l'évolution d'un système : les noeuds et les arêtes sont mutables et leur présence, ou leur absence, a un impact profond sur la structure de la communauté qui les compose.
Dans le cadre de ce mémoire nous présentons une nouvelle méthode de détection de communautés dans les réseaux dynamiques. Contrairement aux méthodes traditionnelles, qui recalcule toute la décomposition de la communauté après chaque modification du réseau, notre méthode prend en compte l’historique des communautés et met à jour la solution en fonction des modifications du réseau via un processus de propagation de labels locaux, qui affecte généralement une petite partie du réseau. L'efficacité de notre algorithme a été testée sur des réseaux réels, ce qui montre qu'elle peut identifier et suivre avec succès les communautés dynamiques. De plus, il peut détecter des communautés de bonne qualité par rapport à d'autres méthodes.Note de contenu : Sommaire
INTRODUCTION GENERALE ...................................................................................... 1
CHAPITRE 1 : LA DETECTION DE COMMUNAUTES DANS LES RESEAUX DYNAMIQUES
1.1. Introduction ......................................................................................................... 3
1.2. Notions relatives aux graphes ............................................................................. 3
1.3. Centralité d’intermédiarité des liens (edge betweenness) ................................... 6
1.4. Modélisation par les graphes .............................................................................. 6
1.4.1. Réseaux sociaux .......................................................................................... 7
1.4.2. Réseaux d'information ................................................................................. 8
1.4.3. Réseaux biologiques .................................................................................... 8
1.5. Graphe de terrain ................................................................................................ 8
1.6. Réseaux dynamique ............................................................................................ 9
1.7. Définitions d’une communauté ........................................................................... 9
1.8. Généralités sur la détection de communautés ................................................... 12
1.8.1. Partitionnement de graphe ......................................................................... 12
1.8.2. Regroupement hiérarchique ....................................................................... 13
1.8.3. Détection de communautés ........................................................................ 14
1.9. Conclusion ........................................................................................................ 15
CHAPITRE 2 : ETAT DE L'ART
2.1. Introduction ....................................................................................................... 16
2.2. Approches de détection de communautés statiques .......................................... 16
2.3. Approches de détection de communautés dynamiques .................................... 22
2.3.1. Approches par détections statiques successives (Independent Community Detections and Matching) ........................................................................................ 22
2.3.2. Approches par détections statiques informées successives (Informed Iterative Community Detections) ............................................................................. 26
2.3.3. Approches par étude simultanée de toutes les étapes d’évolution (Global Community Detection on All Snapshots) ................... 28
2.3.4. Approches travaillant sur des réseaux temporels (Dynamic Community Detection on Temporal Networks) .................. 30
2.4. Conclusion ........................................................................... 32
CHAPITRE 3 : CONCEPTION ET IMPLEMENTATION
3.1. Introduction ................................................................... 33
3.2. Noeud infecté ..................................................................................................... 33
3.3. Propagation de labels ........................................................................................ 33
3.4. Mise à jour des communautés ........................................................................... 34
3.5. Conclusion ........................................................................................................ 41
CHAPITRE 4 : EXPERIMENTATIONS ET RESULTATS
4.1. Introduction ....................................................................................................... 42
4.2. Mesures de qualité ............................................................................................ 42
4.2.1. La Modularité ............................................................................................ 42
4.2.2. La mesure de l’information mutuelle normalisée (The Normalized Mutual Information measure NMI) ........ 43
4.3. Expérimentations sur réseaux statique .............................................................. 43
4.3.1. Championnat de football d’Angleterre ...................................................... 44
4.3.2. Les députés au Royaume-Uni .................................................................... 44
4.3.3. Cercles sociaux : Facebook ....................................................................... 45
4.4. Expérimentations sur réseau dynamique .......................................................... 47
Systèmes autonomes – Oregon1 .............................................................................. 47
4.5. Conclusion ........................................................................................................ 49
CONCLUSION GENERALE ........................................................................................ 50
BIBLIOGRAPHIE ......................................................................................................... 51
Côte titre : MAI/0254 En ligne : https://drive.google.com/file/d/1iH57LsqZShgSRhNiIyTYtFihLH33wssG/view?usp=shari [...] Format de la ressource électronique : Detection de communautes dans les reseaux dynamiques [texte imprimé] / Douadi, Asma, Auteur ; Kamel, Nadjet, Directeur de thèse . - [S.l.] : Setif:UFA, 2018 . - 1 vol (51 f .) ; 29 cm.
Langues : Français (fre) Langues originales : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Détection de communautés
Réseaux dynamiques
Réseaux temporels
Evolution des commnautésIndex. décimale : 004 Informatique Résumé : Résumé
Plusieurs études ont montré que les réseaux modélisant des phénomènes du monde réel sont caractérisés par des propriétés remarquables : ils sont organisés en fonction de la structure de la communauté et cette dernière évolue avec le temps. De nombreux chercheurs ont travaillé sur des méthodes permettant de dévoiler efficacement des sous-structures dans les réseaux, donnant naissance au domaine de la détection de communauté. Les réseaux dynamiques peuvent être utilisés pour modéliser l'évolution d'un système : les noeuds et les arêtes sont mutables et leur présence, ou leur absence, a un impact profond sur la structure de la communauté qui les compose.
Dans le cadre de ce mémoire nous présentons une nouvelle méthode de détection de communautés dans les réseaux dynamiques. Contrairement aux méthodes traditionnelles, qui recalcule toute la décomposition de la communauté après chaque modification du réseau, notre méthode prend en compte l’historique des communautés et met à jour la solution en fonction des modifications du réseau via un processus de propagation de labels locaux, qui affecte généralement une petite partie du réseau. L'efficacité de notre algorithme a été testée sur des réseaux réels, ce qui montre qu'elle peut identifier et suivre avec succès les communautés dynamiques. De plus, il peut détecter des communautés de bonne qualité par rapport à d'autres méthodes.Note de contenu : Sommaire
INTRODUCTION GENERALE ...................................................................................... 1
CHAPITRE 1 : LA DETECTION DE COMMUNAUTES DANS LES RESEAUX DYNAMIQUES
1.1. Introduction ......................................................................................................... 3
1.2. Notions relatives aux graphes ............................................................................. 3
1.3. Centralité d’intermédiarité des liens (edge betweenness) ................................... 6
1.4. Modélisation par les graphes .............................................................................. 6
1.4.1. Réseaux sociaux .......................................................................................... 7
1.4.2. Réseaux d'information ................................................................................. 8
1.4.3. Réseaux biologiques .................................................................................... 8
1.5. Graphe de terrain ................................................................................................ 8
1.6. Réseaux dynamique ............................................................................................ 9
1.7. Définitions d’une communauté ........................................................................... 9
1.8. Généralités sur la détection de communautés ................................................... 12
1.8.1. Partitionnement de graphe ......................................................................... 12
1.8.2. Regroupement hiérarchique ....................................................................... 13
1.8.3. Détection de communautés ........................................................................ 14
1.9. Conclusion ........................................................................................................ 15
CHAPITRE 2 : ETAT DE L'ART
2.1. Introduction ....................................................................................................... 16
2.2. Approches de détection de communautés statiques .......................................... 16
2.3. Approches de détection de communautés dynamiques .................................... 22
2.3.1. Approches par détections statiques successives (Independent Community Detections and Matching) ........................................................................................ 22
2.3.2. Approches par détections statiques informées successives (Informed Iterative Community Detections) ............................................................................. 26
2.3.3. Approches par étude simultanée de toutes les étapes d’évolution (Global Community Detection on All Snapshots) ................... 28
2.3.4. Approches travaillant sur des réseaux temporels (Dynamic Community Detection on Temporal Networks) .................. 30
2.4. Conclusion ........................................................................... 32
CHAPITRE 3 : CONCEPTION ET IMPLEMENTATION
3.1. Introduction ................................................................... 33
3.2. Noeud infecté ..................................................................................................... 33
3.3. Propagation de labels ........................................................................................ 33
3.4. Mise à jour des communautés ........................................................................... 34
3.5. Conclusion ........................................................................................................ 41
CHAPITRE 4 : EXPERIMENTATIONS ET RESULTATS
4.1. Introduction ....................................................................................................... 42
4.2. Mesures de qualité ............................................................................................ 42
4.2.1. La Modularité ............................................................................................ 42
4.2.2. La mesure de l’information mutuelle normalisée (The Normalized Mutual Information measure NMI) ........ 43
4.3. Expérimentations sur réseaux statique .............................................................. 43
4.3.1. Championnat de football d’Angleterre ...................................................... 44
4.3.2. Les députés au Royaume-Uni .................................................................... 44
4.3.3. Cercles sociaux : Facebook ....................................................................... 45
4.4. Expérimentations sur réseau dynamique .......................................................... 47
Systèmes autonomes – Oregon1 .............................................................................. 47
4.5. Conclusion ........................................................................................................ 49
CONCLUSION GENERALE ........................................................................................ 50
BIBLIOGRAPHIE ......................................................................................................... 51
Côte titre : MAI/0254 En ligne : https://drive.google.com/file/d/1iH57LsqZShgSRhNiIyTYtFihLH33wssG/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0254 MAI/0254 Mémoire Bibliothéque des sciences Français Disponible
Disponible