Titre : |
Découverte de communautés dynamiques dans les réseaux temporels |
Type de document : |
texte imprimé |
Auteurs : |
Benaggoun, samir ; DRIF, AHLEM, Directeur de thèse |
Editeur : |
Setif:UFA |
Année de publication : |
2017 |
Importance : |
1 vol (77f.) |
Format : |
29 cm |
Langues : |
Français (fre) |
Catégories : |
Thèses & Mémoires:Informatique
|
Mots-clés : |
Réseaux
Systèmes Distribués
Modularité
communautés dynamiques
Réseaux sociaux
Réseaux temporels |
Index. décimale : |
004 Informatique |
Résumé : |
RESUMÉ
L’analyse de réseaux sociaux est un outil qui s’impose dans de nombreuses
sciences. Un de ces outils spécifiques à l’analyse est la détection de communautés.
Si le domaine de la détection de communautés statiques sans recouvrement semble
aujourd’hui arrivé à maturité, avec plusieurs méthodes se révélant à la fois rapides,
performantes, nous pensons que le problème de la détection de communautés avec
recouvrement n’a pas encore atteint ce stade, Quant aux communautés dynamiques,
nous pensons que l’on est encore dans une phase d’exploration, ce qui explique la
grande variété d’approches utilisées. L’objectif de ce travail est de proposer une
nouvelle approche de détection de communautés qui serait capable de détecter
l’évolution des communautés au cours du temps pour des réseaux sociaux. Pour
cela, nous avons défini une nouvelle méthode qui fonctionne en deux phases. Durant la première phase, nous détectons tous les groupes similaire afin de décomposer
le réseau initial en petits groupes élémentaires c’est à dire faire du Clustering (par la
méthode de Louvain). Dans la deuxième phase, nous proposons une procédure itérative ayant pour objectif l'identification des différentes communautés avec l’analyse
des déplacements des nœuds d’une communauté à une autre, Et au fur et à mesure
on évalue la modularité en utilisant les actions de mise à jour (ajout nœud, suppression nœud, update nœud) jusqu’à atteindre une modularité Optimale. La performance de l’approche proposée est comparée avec d'autres algorithmes de détection
de communautés qui montre l’efficacité de notre approche. |
Note de contenu : |
Table des matières
Introduction Générale.............................................................................................. 1
Chapitre 1 : Communauté et réseaux complexes
1. Introduction ........................................................................................................... 5
2. Représentation des Graphes ................................................................................. 5
2.1 La matrice d'adjacence ............................................................................................................5
2.1 Matrice d’incidence.................................................................................................................6
2.3 Laplacien Subordonné à un Graphe .......................................................................................7
2.4 Graphes Dynamiques..............................................................................................................8
3. Propriétés et conjectures....................................................................................... 8
3.1 Nombre chromatique et le degré maximal .........................................................................8
3.2 Coefficient de regroupement..................................................................................................9
3.2.1 Définition ..........................................................................................................................9
3.2.2 Coefficient global..............................................................................................................9
3.3 La centralité d’intermédiarité des liens...............................................................................10
4. Les Communautés ............................................................................................... 11
4.1 Définition ...............................................................................................................................11
4.2 Définitions comparatives.......................................................................................................11
4.3 Définitions de référence individuelle ...................................................................................12
4.4 Représentation graphique des communautés ........................................................................12
4.5 Modularité ..............................................................................................................13
5. Réseaux Complexes.............................................................................................. 14
5.1 Réseaux sociaux....................................................................................................................15
5.2 Réseaux biologiques..............................................................................................................15
5.3 Réseaux d’information ..........................................................................................................15
5.4 Réseaux technologiques........................................................................................................16
5.5 Réseaux linguistiques............................................................................................................16
6. Conclusion............................................................................................................ 16
Chapitre 2 : L'Etat de l'art
1. Introduction ......................................................................................................... 20
2. Méthodes de découverte de communautés dans les réseaux Complexes.......... 20
2.1 Algorithme Basique de Betweenness.....................................................................................21
2.1.1 Idée fondamentale ...............................................................................................21
2.1.2 Mesure de communautés.................................................................................................21
2.1.3 Méthode de détection des communautés........................................................................23
2.1.4 Exemple d’expérimentation ...........................................................................................23
2.1.5. Discussion .......................................................................................................................24
2.2 Fast algorithm........................................................................................................................24
2.2.1 Idée fondamentale ..........................................................................................................24
2.2.2 Mesure de communautés................................................................................................24
2.2.4 Exemple d’expérimentation ..........................................................................................25
2.2.5 Discussion ......................................................................................................................26
2.3 Extremal optimization algorithm ..........................................................................................27
2.3.1 Idée fondamentale ..........................................................................................................27
2.3.2 Mesure de communautés................................................................................................27
2.3.3 Méthode de découverte de communautés ......................................................................27
2.3.4 Exemple d’expérimentation ...........................................................................................28
2.3.5. Discussion .......................................................................................................................28
3. Opérations de communautés................................................................................ 29
3.1 Différentes approches.............................................................................................................30
3.1.1 Approches par détections statiques successives..............................................................30
3.1.2 Avec communautés non recouvrantes............................................................................31
3.1.3 Avec communautés recouvrantes..................................................................................31
3.1.4 Approches travaillant sur des réseaux temporels .............................................................33
4. Conclusion........................................................................................................... 35
Chapitre 3 : Méthode proposée pour la détection de communauté
1. Introduction .......................................................................................................... 38
2. Algorithme de Louvain......................................................................................... 38
2.1 Description de l’algorithme....................................................................................................38
2.2 Organigramme de l’algorithme ..............................................................................................40
2.3 Exemple de détection de communautés pour des réseaux sociaux ........................................42
3. Proposition d’une extension de l’algorithme de Louvain pour les réseaux temporels ......................................... 43
3.1 Description de l’approche proposée.......................................................................................43
3.2 Evolution des évènements au cours du temps........................................................................44
3.3 Détails des opérations de mise à jour...................................................................................45
3.3.1 Evènement de création de Nœud....................................................................................45
3.3.2 Evènement de modification des voisins d’un Nœud (Update)......................................45
3.3.3 Evènement de suppression d’un Nœud ..........................................................................46
3.4 Méthodes et classes utilisées pour les opérations de mise à jour ........................................47
3.5 Organigramme de la dynamique des communautés.............................................................50
4. Conclusion........................................................................................................... 51
Chapitre 4 : Evaluation et expérimentation
1 .Introduction .......................................................................................................... 53
2. Les langages utilisés et les outils d'implémentations .......................................... 53
2.1.2 Langage GML ................................................................................................................53
2.2 Les outils utilisés....................................................................................................................54
2.2.1 Outil de visualisation Gephi..........................................................................................54
2.2.2 NetBeans.........................................................................................................................54
3. Jeux de données.................................................................................................... 55
3.1 Eurovision dataset ..................................................................................................................55
3.1.1 Format du fichier..............................................................................................................55
3.1.2 visualisation d’un fichier CSV ........................................................................................56
3.2 Distribution des degrés..........................................................................................................56
3.3 Modularité du graphe généré................................................................................................58
4. Interfaces de notre application de découverte dynamique ................................... 58
4.1 Interface d’accueil...................................................................................................................58
4.2 Principe de fonctionnement de l’application.........................................................................60
5. Evaluation des Performances de l’algorithme proposé ..................................... 64
5.1 Analyse de la dynamique .......................................................................................................65
5.2 Détection de communauté durant des instantanés successive................................................65
5.3 Comparaisons de notre approche proposée .............................................................................65
6. Conclusion........................................................................................................... 67
7. Conclusion Générale ......................................................................................... 68
Annexes.................................................................................................................... 69 |
Côte titre : |
MAI/0164 |
En ligne : |
https://drive.google.com/file/d/1RuMZcnT6c2tYnWPDgZzr1I3axvksT8O_/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
Découverte de communautés dynamiques dans les réseaux temporels [texte imprimé] / Benaggoun, samir ; DRIF, AHLEM, Directeur de thèse . - [S.l.] : Setif:UFA, 2017 . - 1 vol (77f.) ; 29 cm. Langues : Français ( fre)
Catégories : |
Thèses & Mémoires:Informatique
|
Mots-clés : |
Réseaux
Systèmes Distribués
Modularité
communautés dynamiques
Réseaux sociaux
Réseaux temporels |
Index. décimale : |
004 Informatique |
Résumé : |
RESUMÉ
L’analyse de réseaux sociaux est un outil qui s’impose dans de nombreuses
sciences. Un de ces outils spécifiques à l’analyse est la détection de communautés.
Si le domaine de la détection de communautés statiques sans recouvrement semble
aujourd’hui arrivé à maturité, avec plusieurs méthodes se révélant à la fois rapides,
performantes, nous pensons que le problème de la détection de communautés avec
recouvrement n’a pas encore atteint ce stade, Quant aux communautés dynamiques,
nous pensons que l’on est encore dans une phase d’exploration, ce qui explique la
grande variété d’approches utilisées. L’objectif de ce travail est de proposer une
nouvelle approche de détection de communautés qui serait capable de détecter
l’évolution des communautés au cours du temps pour des réseaux sociaux. Pour
cela, nous avons défini une nouvelle méthode qui fonctionne en deux phases. Durant la première phase, nous détectons tous les groupes similaire afin de décomposer
le réseau initial en petits groupes élémentaires c’est à dire faire du Clustering (par la
méthode de Louvain). Dans la deuxième phase, nous proposons une procédure itérative ayant pour objectif l'identification des différentes communautés avec l’analyse
des déplacements des nœuds d’une communauté à une autre, Et au fur et à mesure
on évalue la modularité en utilisant les actions de mise à jour (ajout nœud, suppression nœud, update nœud) jusqu’à atteindre une modularité Optimale. La performance de l’approche proposée est comparée avec d'autres algorithmes de détection
de communautés qui montre l’efficacité de notre approche. |
Note de contenu : |
Table des matières
Introduction Générale.............................................................................................. 1
Chapitre 1 : Communauté et réseaux complexes
1. Introduction ........................................................................................................... 5
2. Représentation des Graphes ................................................................................. 5
2.1 La matrice d'adjacence ............................................................................................................5
2.1 Matrice d’incidence.................................................................................................................6
2.3 Laplacien Subordonné à un Graphe .......................................................................................7
2.4 Graphes Dynamiques..............................................................................................................8
3. Propriétés et conjectures....................................................................................... 8
3.1 Nombre chromatique et le degré maximal .........................................................................8
3.2 Coefficient de regroupement..................................................................................................9
3.2.1 Définition ..........................................................................................................................9
3.2.2 Coefficient global..............................................................................................................9
3.3 La centralité d’intermédiarité des liens...............................................................................10
4. Les Communautés ............................................................................................... 11
4.1 Définition ...............................................................................................................................11
4.2 Définitions comparatives.......................................................................................................11
4.3 Définitions de référence individuelle ...................................................................................12
4.4 Représentation graphique des communautés ........................................................................12
4.5 Modularité ..............................................................................................................13
5. Réseaux Complexes.............................................................................................. 14
5.1 Réseaux sociaux....................................................................................................................15
5.2 Réseaux biologiques..............................................................................................................15
5.3 Réseaux d’information ..........................................................................................................15
5.4 Réseaux technologiques........................................................................................................16
5.5 Réseaux linguistiques............................................................................................................16
6. Conclusion............................................................................................................ 16
Chapitre 2 : L'Etat de l'art
1. Introduction ......................................................................................................... 20
2. Méthodes de découverte de communautés dans les réseaux Complexes.......... 20
2.1 Algorithme Basique de Betweenness.....................................................................................21
2.1.1 Idée fondamentale ...............................................................................................21
2.1.2 Mesure de communautés.................................................................................................21
2.1.3 Méthode de détection des communautés........................................................................23
2.1.4 Exemple d’expérimentation ...........................................................................................23
2.1.5. Discussion .......................................................................................................................24
2.2 Fast algorithm........................................................................................................................24
2.2.1 Idée fondamentale ..........................................................................................................24
2.2.2 Mesure de communautés................................................................................................24
2.2.4 Exemple d’expérimentation ..........................................................................................25
2.2.5 Discussion ......................................................................................................................26
2.3 Extremal optimization algorithm ..........................................................................................27
2.3.1 Idée fondamentale ..........................................................................................................27
2.3.2 Mesure de communautés................................................................................................27
2.3.3 Méthode de découverte de communautés ......................................................................27
2.3.4 Exemple d’expérimentation ...........................................................................................28
2.3.5. Discussion .......................................................................................................................28
3. Opérations de communautés................................................................................ 29
3.1 Différentes approches.............................................................................................................30
3.1.1 Approches par détections statiques successives..............................................................30
3.1.2 Avec communautés non recouvrantes............................................................................31
3.1.3 Avec communautés recouvrantes..................................................................................31
3.1.4 Approches travaillant sur des réseaux temporels .............................................................33
4. Conclusion........................................................................................................... 35
Chapitre 3 : Méthode proposée pour la détection de communauté
1. Introduction .......................................................................................................... 38
2. Algorithme de Louvain......................................................................................... 38
2.1 Description de l’algorithme....................................................................................................38
2.2 Organigramme de l’algorithme ..............................................................................................40
2.3 Exemple de détection de communautés pour des réseaux sociaux ........................................42
3. Proposition d’une extension de l’algorithme de Louvain pour les réseaux temporels ......................................... 43
3.1 Description de l’approche proposée.......................................................................................43
3.2 Evolution des évènements au cours du temps........................................................................44
3.3 Détails des opérations de mise à jour...................................................................................45
3.3.1 Evènement de création de Nœud....................................................................................45
3.3.2 Evènement de modification des voisins d’un Nœud (Update)......................................45
3.3.3 Evènement de suppression d’un Nœud ..........................................................................46
3.4 Méthodes et classes utilisées pour les opérations de mise à jour ........................................47
3.5 Organigramme de la dynamique des communautés.............................................................50
4. Conclusion........................................................................................................... 51
Chapitre 4 : Evaluation et expérimentation
1 .Introduction .......................................................................................................... 53
2. Les langages utilisés et les outils d'implémentations .......................................... 53
2.1.2 Langage GML ................................................................................................................53
2.2 Les outils utilisés....................................................................................................................54
2.2.1 Outil de visualisation Gephi..........................................................................................54
2.2.2 NetBeans.........................................................................................................................54
3. Jeux de données.................................................................................................... 55
3.1 Eurovision dataset ..................................................................................................................55
3.1.1 Format du fichier..............................................................................................................55
3.1.2 visualisation d’un fichier CSV ........................................................................................56
3.2 Distribution des degrés..........................................................................................................56
3.3 Modularité du graphe généré................................................................................................58
4. Interfaces de notre application de découverte dynamique ................................... 58
4.1 Interface d’accueil...................................................................................................................58
4.2 Principe de fonctionnement de l’application.........................................................................60
5. Evaluation des Performances de l’algorithme proposé ..................................... 64
5.1 Analyse de la dynamique .......................................................................................................65
5.2 Détection de communauté durant des instantanés successive................................................65
5.3 Comparaisons de notre approche proposée .............................................................................65
6. Conclusion........................................................................................................... 67
7. Conclusion Générale ......................................................................................... 68
Annexes.................................................................................................................... 69 |
Côte titre : |
MAI/0164 |
En ligne : |
https://drive.google.com/file/d/1RuMZcnT6c2tYnWPDgZzr1I3axvksT8O_/view?usp=shari [...] |
Format de la ressource électronique : |
pdf |
|