University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur DRIF, AHLEM |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Algorithme de contrôle de topologie dans les réseaux Ad Hoc Type de document : texte imprimé Auteurs : MEBARKIA, Ossama ; DRIF, AHLEM, Directeur de thèse Editeur : Setif:UFA Année de publication : 2012 Importance : 1 vol (64f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
algorithme
topologie
réseaux Ad HocIndex. décimale : 004 Informatique Résumé : Conclusion
Les réseaux sans fil de type ad hoc sont des réseaux caractérisés par des ressources limitées en énergie. La conservation d'énergie s'avère donc être un facteur primordial pour la durée de vie du réseau. La technologie de batterie a été évoluée parallèlement aux avancements en technologie de communications sans fil. Actuellement la capacité de batteries ne peut pas être sensiblement améliorée, des efforts devraient être mis dans la conception des logiciels et des matériels d'énergie-efficace. Les dispositifs mobiles portatifs ont typiquement plusieurs composants hardware qui consomment la puissance de batterie, ces principaux matériels sont: écran d'affichage, disque, CPU, mémoire, et la carte d'interface sans fil (WNIC: Wireless Network Interface Card). Plusieurs travaux ont démontré que l'activité réseau est très coûteuse en énergie et que le composant WNIC peut consommer de 10 à 50% d'énergie totale du système. L'émission ainsi que la réception consomment une énergie importante. Toutes ces activités engendrent une dissipation d'énergie inadmissible dans les environnements ad hoc mobile. L'énergie consommée par un nœud est également en fonction de ses activités réseau au niveau des différentes couches.
Dans ce projet, nous nous somme penché sur les approches de contrôle de topologie, nous avons étudié le fonctionnement des trois catégories de ces approches. Les approches à base de localisation supposent que les informations les plus précises sur les positions des nœuds sont connues à l’exemple du protocole R&M. Les approches à base de direction estiment la direction relative de leurs voisins. Les approches de type voisinage sont basés sur le graphe k-voisins, c.est à dire le graphe dans lequel chaque nœud est relié à ses k voisins les plus proches.
Notre travail se fonde sur les approches de type voisinage en utilisant l’arbre MST et le sous graphe Power Spanner. Nous avons tirer profit de la capacité des nœuds de déterminer le nombre et l'identité de voisins dans le rang de transmission maximum pour établir une structure sur cet ensemble de voisin en tenant compte aux paramètres énergétiques. L’analyse et l’évaluation des deux algorithmes, nous a permis de conclure que le choix d'une meilleure stratégie pour augmenter la durée de vie de réseaux est liées aux plusieurs critères.
Nous envisageons dans un futur travail d’implémenter d’autre structure optimale en tirant profit des sous graphes possédant des propriétés satisfaisantes pour être appliquer comme des topologies virtuelle optimale .
Note de contenu : Table des matières
Introduction générale 5
I Les Réseaux mobile Ad Hoc 7
I.1. Introduction 7
I.2. Les environnements mobiles 8
I.2.1 Les r´eseaux avec infrastructure 8
I.2.2 Les réseaux sans infrastructure 9
I.3. Les reseaux ad hoc 10
I.4. Modélisation d’un réseau ad hoc 11
I.5. Caractéristiques des réseaux ad hoc 12
I.6. Application des réseaux ad hoc 14
I.7. Avantage des réseaux ad-hoc 15
I.8. Conclusion 16
II La conservation d’énergie dans réseaux Ad Hoc 17
II.1 Introduction 17
II.2 Conservation d’énergie dans les réseaux ad hoc 18
II.3 Source de perte d’énergie 18
 Le mode inactif: 18
 Les collisions: 18
 Le sur débit des protocoles: 19
 Taux d’erreurs élevé: 19
II.3.1 Exemple d’épuisement d’une batterie du nœud : 19
II.4 Approche existante de la consommation d’énergie 20
II.4.1 Au niveau routage 20
a. MPTR (Minimum Total Transmission Power Routing) 20
b. MBCR (Minimum Battery Cost Routing) 21
c. MMBCR (Min Max Battery Cost Routing) 21
d. E-DSR(Energy Dynamic Source Routing) 22
e. EC-DSR (Energy Conserving Dynamic Source Routing) 22
II.4.2 Au niveau liaison de données 22
a. La couche MAC 22
II.4.3 Au niveau contrôle de topologie 23
II.5 Impact de la mobilité sur la conservation d'énergie 23
II.6 Conclusion 24
III. Protocole de contrôle de topologie 26
III.1 Introduction 26
III.2 Contrôle de topologie et conservation d’énergie 27
III.3 Mécanisme de contrôle de topologie 28
III.4 Taxonomie des protocoles de contrôle de topologie 29
III. 4.1 Les approches CTR homogène et Non homogène 29
III.4.2 Les approches de contrôle de topologie à base de localisation 30
III.4.3 Les approches de contrôle de topologie basée sur la direction 30
III.4.4 Les approches de contrôle de topologie basée sur le voisinage 30
III.4.5 Le per-paquet et le contrôle de topologie périodique 30
III.5 Les protocoles de contrôle de topologie 31
III.5.2 Le protocole R&M (Rodoplu et Meng 1999) 31
III.5.2 Le protocole MST (minimum Spanning Tree) 34
III.5.3 Le protocole LMST 35
III.5.4 Le protocole RNG (Relative Neighbordhood Graph) 37
III.6 Conclusion 39
IV. Simulation des algorithmes de contrôle de topologie 40
IV.1 Introduction 40
IV.2 Outils de simulation 41
IV.3 Présentation du simulateur NS2 41
IV.4 Pourquoi le simulateur NS-2 ? 42
IV.5 Le principe du simulateur NS2 43
IV.5.1 Le langage script TCL 44
IV.5.2 L'outil de visualisation NAM 44
IV.5.3 Format d’un fichier trace 44
IV.6 Evaluation des algorithmes de contrôle de topologie 45
IV.6.1 Les algorithmes de contrôle de topologie 45
IV.6.2 Préliminaires 45
IV.6.3 Modèle énergétique 46
IV.6.4 Algorithme des graphes (Power spanner) 47
IV.6.5 Algorithme MST (Minimum Spanning Tree) 48
IV.7 Simulation et études de performances 50
IV.7.1 Les paramètres de la simulation 50
IV.7.2 Les scenarios de la simulation 50
IV.7.3 Résultats de simulation 54
IV.8 Conclusion 56
Conclusion 57
Référence bibliographique 58
Annexe 61
Côte titre : MAI/0022 En ligne : https://drive.google.com/file/d/1h1gnC9jXpR0iDF7uLNC7UGkZRK8TjLCE/view?usp=shari [...] Format de la ressource électronique : docx Algorithme de contrôle de topologie dans les réseaux Ad Hoc [texte imprimé] / MEBARKIA, Ossama ; DRIF, AHLEM, Directeur de thèse . - [S.l.] : Setif:UFA, 2012 . - 1 vol (64f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
algorithme
topologie
réseaux Ad HocIndex. décimale : 004 Informatique Résumé : Conclusion
Les réseaux sans fil de type ad hoc sont des réseaux caractérisés par des ressources limitées en énergie. La conservation d'énergie s'avère donc être un facteur primordial pour la durée de vie du réseau. La technologie de batterie a été évoluée parallèlement aux avancements en technologie de communications sans fil. Actuellement la capacité de batteries ne peut pas être sensiblement améliorée, des efforts devraient être mis dans la conception des logiciels et des matériels d'énergie-efficace. Les dispositifs mobiles portatifs ont typiquement plusieurs composants hardware qui consomment la puissance de batterie, ces principaux matériels sont: écran d'affichage, disque, CPU, mémoire, et la carte d'interface sans fil (WNIC: Wireless Network Interface Card). Plusieurs travaux ont démontré que l'activité réseau est très coûteuse en énergie et que le composant WNIC peut consommer de 10 à 50% d'énergie totale du système. L'émission ainsi que la réception consomment une énergie importante. Toutes ces activités engendrent une dissipation d'énergie inadmissible dans les environnements ad hoc mobile. L'énergie consommée par un nœud est également en fonction de ses activités réseau au niveau des différentes couches.
Dans ce projet, nous nous somme penché sur les approches de contrôle de topologie, nous avons étudié le fonctionnement des trois catégories de ces approches. Les approches à base de localisation supposent que les informations les plus précises sur les positions des nœuds sont connues à l’exemple du protocole R&M. Les approches à base de direction estiment la direction relative de leurs voisins. Les approches de type voisinage sont basés sur le graphe k-voisins, c.est à dire le graphe dans lequel chaque nœud est relié à ses k voisins les plus proches.
Notre travail se fonde sur les approches de type voisinage en utilisant l’arbre MST et le sous graphe Power Spanner. Nous avons tirer profit de la capacité des nœuds de déterminer le nombre et l'identité de voisins dans le rang de transmission maximum pour établir une structure sur cet ensemble de voisin en tenant compte aux paramètres énergétiques. L’analyse et l’évaluation des deux algorithmes, nous a permis de conclure que le choix d'une meilleure stratégie pour augmenter la durée de vie de réseaux est liées aux plusieurs critères.
Nous envisageons dans un futur travail d’implémenter d’autre structure optimale en tirant profit des sous graphes possédant des propriétés satisfaisantes pour être appliquer comme des topologies virtuelle optimale .
Note de contenu : Table des matières
Introduction générale 5
I Les Réseaux mobile Ad Hoc 7
I.1. Introduction 7
I.2. Les environnements mobiles 8
I.2.1 Les r´eseaux avec infrastructure 8
I.2.2 Les réseaux sans infrastructure 9
I.3. Les reseaux ad hoc 10
I.4. Modélisation d’un réseau ad hoc 11
I.5. Caractéristiques des réseaux ad hoc 12
I.6. Application des réseaux ad hoc 14
I.7. Avantage des réseaux ad-hoc 15
I.8. Conclusion 16
II La conservation d’énergie dans réseaux Ad Hoc 17
II.1 Introduction 17
II.2 Conservation d’énergie dans les réseaux ad hoc 18
II.3 Source de perte d’énergie 18
 Le mode inactif: 18
 Les collisions: 18
 Le sur débit des protocoles: 19
 Taux d’erreurs élevé: 19
II.3.1 Exemple d’épuisement d’une batterie du nœud : 19
II.4 Approche existante de la consommation d’énergie 20
II.4.1 Au niveau routage 20
a. MPTR (Minimum Total Transmission Power Routing) 20
b. MBCR (Minimum Battery Cost Routing) 21
c. MMBCR (Min Max Battery Cost Routing) 21
d. E-DSR(Energy Dynamic Source Routing) 22
e. EC-DSR (Energy Conserving Dynamic Source Routing) 22
II.4.2 Au niveau liaison de données 22
a. La couche MAC 22
II.4.3 Au niveau contrôle de topologie 23
II.5 Impact de la mobilité sur la conservation d'énergie 23
II.6 Conclusion 24
III. Protocole de contrôle de topologie 26
III.1 Introduction 26
III.2 Contrôle de topologie et conservation d’énergie 27
III.3 Mécanisme de contrôle de topologie 28
III.4 Taxonomie des protocoles de contrôle de topologie 29
III. 4.1 Les approches CTR homogène et Non homogène 29
III.4.2 Les approches de contrôle de topologie à base de localisation 30
III.4.3 Les approches de contrôle de topologie basée sur la direction 30
III.4.4 Les approches de contrôle de topologie basée sur le voisinage 30
III.4.5 Le per-paquet et le contrôle de topologie périodique 30
III.5 Les protocoles de contrôle de topologie 31
III.5.2 Le protocole R&M (Rodoplu et Meng 1999) 31
III.5.2 Le protocole MST (minimum Spanning Tree) 34
III.5.3 Le protocole LMST 35
III.5.4 Le protocole RNG (Relative Neighbordhood Graph) 37
III.6 Conclusion 39
IV. Simulation des algorithmes de contrôle de topologie 40
IV.1 Introduction 40
IV.2 Outils de simulation 41
IV.3 Présentation du simulateur NS2 41
IV.4 Pourquoi le simulateur NS-2 ? 42
IV.5 Le principe du simulateur NS2 43
IV.5.1 Le langage script TCL 44
IV.5.2 L'outil de visualisation NAM 44
IV.5.3 Format d’un fichier trace 44
IV.6 Evaluation des algorithmes de contrôle de topologie 45
IV.6.1 Les algorithmes de contrôle de topologie 45
IV.6.2 Préliminaires 45
IV.6.3 Modèle énergétique 46
IV.6.4 Algorithme des graphes (Power spanner) 47
IV.6.5 Algorithme MST (Minimum Spanning Tree) 48
IV.7 Simulation et études de performances 50
IV.7.1 Les paramètres de la simulation 50
IV.7.2 Les scenarios de la simulation 50
IV.7.3 Résultats de simulation 54
IV.8 Conclusion 56
Conclusion 57
Référence bibliographique 58
Annexe 61
Côte titre : MAI/0022 En ligne : https://drive.google.com/file/d/1h1gnC9jXpR0iDF7uLNC7UGkZRK8TjLCE/view?usp=shari [...] Format de la ressource électronique : docx Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0022 MAI/0022 Mémoire Bibliothéque des sciences Anglais Disponible
Disponible
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 temporelsIndex. 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.................................................................................................................... 69Côte titre : MAI/0164 En ligne : https://drive.google.com/file/d/1RuMZcnT6c2tYnWPDgZzr1I3axvksT8O_/view?usp=shari [...] Format de la ressource électronique : 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 temporelsIndex. 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.................................................................................................................... 69Côte titre : MAI/0164 En ligne : https://drive.google.com/file/d/1RuMZcnT6c2tYnWPDgZzr1I3axvksT8O_/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0164 MAI/0164 Mémoire Bibliothéque des sciences Français Disponible
Disponible