University Sétif 1 FERHAT ABBAS Faculty of Sciences
Détail de l'auteur
Auteur Kebbab,naouel |
Documents disponibles écrits par cet auteur
Ajouter le résultat dans votre panier Affiner la recherche
Titre : Apprentissage automatique dans les réseaux sociaux Type de document : texte imprimé Auteurs : Kebbab,naouel ; A Moussaoui, Directeur de thèse Editeur : Setif:UFA Année de publication : 2016 Importance : 1 vol (52f.) Format : 29 cm Langues : Français (fre) Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
apprentissage automatique
réseaux sociauxIndex. décimale : 004 Informatique Résumé : Résumé
Dans les grands réseaux, la détection de sous-ensembles de sommets plus densément
connectés que d’autres, appelés des communautés, est un problème que l’on retrouve dans
plusieurs disciplines : Biologie (réseaux d’interactions entre protéines), Informatique
(recherche d’informations sur le Web), mais aussi, Sociologie (groupes dans des réseaux
sociaux). Ces communautés jouent un rôle important dans l’organisation ou la structuration
des réseaux.
De fait, il s’agit de déterminer des classes dans un graphe. Ce problème est donc
fortement lié à celui du partitionnement, avec la spécificité suivante : suivant l’usage que
l’on veut faire de ces communautés, les classes peuvent (doivent) être disjointes ou non. En
Biologie, où l’on analyse 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.
Ainsi, les méthodes traditionnelles en Classification peuvent être utilisées ; en
particulier 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, 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.
Cette approche originale basée sur les techniques de Data Mining pour l’extraction
des connaissances, est l’algorithme FCM (Fuzzy C-Means).
Une étude de performances, dans laquelle nos méthodes sont testés sur des différents
graphes réels atteste de leur pertinence.Note de contenu : Table des matières
Remerciements
Résumé
Table des matières
Table de figures
Introduction Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..…. 1
1 Data Mining
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 3
1.2 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Entrepôts de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 4
1.4 Le Data Mining est né de . . . . . . . . . . . . . . . . . . . . . …. . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Data Mining et KDD (Knowledge Data Discovery) . . . .. . . . . . . . . . . . .. . . . . . …. 5
1.6 DM : les raisons du développement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.7 Mise en œuvre d’un projet de DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.8 Caractérisation des méthodes de DM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.8.1 DM : une nouvelle conception de la statistique et du rôle des modèles. . . . . . . . .6
1.8.2 Tâches du Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 7
1.8.2.1 Classification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.8.2.2 Clustering(Segmentation) . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .8
1.8.2.3 Règles d’association . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8.2.4 Recherche de séquences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
1.8.2.5 Détection de déviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … . . .9
1.9 Techniques et algorithmes de DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9.1Classification supervisé. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 10
1.9.1.1 Les arbres de décision. . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . . . .. . . . . .10
1.9.1.2 Les réseaux de neurones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 11
1.9.1.3 Classification bayésienne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9.1.4 Support Vecteurs Machine(SVM) . . . . . . . . .. .. .. .. . . . . .. .. . . . . . .. .. . . 13
1.9.1.5 k plus proches voisins. . . . .. .. . . . . . .. . . .. . . . . . .. . . . . .. . . .. . .. . . . . .. .13
1.9.2 Classification non-supervisé(Automatique). . . . . . . . . . . . . . . . . . . . . . . . . . . .14
1.9.2.1 Classification hiérarchique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
1.9.2.2 Classification par densité . . . . . . . . . . . .. . . . . . . . . … .. .. . . .. . . .. .. . . . .15
1.9.2.3 Classification par partition. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . .16
1.10 Conclusion. . . . . . . . .. . . . . .. . . . . . .. . . . . . . . . . .. . . . . . .. . . .. .. . . . . . . . .. . . 16
2 Détection De Communautés Dans Les Réseaux Sociaux
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Concepts. . . . . . . .. . .. . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Qu’est-ce qu’un réseau social. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
2.2.2 Communauté . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. .. . . . . . 18
2.2.3 La détection de communautés. . . . .. . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Exemples de réseaux sociaux . . . . . . . . . . . . . .. . . . . . . . . .. .. . . .. . . . . . . . . . . . . . 18
2.3.1 Club de karaté du Zachary. .. . .. .. . . . . . . .. .. .. . .. . . .. .. . . . . .. . . . . . .. . . ... . 18
2.3.2 Le graphe de Pages Web. . . . . . . .. . . . . . . . . . . . . . .. . . . . .. . . . . . . .. . . . . . . . 19
2.4 Analyse des réseaux sociaux. . . . . . . . .. . .. . . . . . . . . . . . . . . . . . .. . . . . . . . 19
2.5 Caractéristique d’un réseau social. . . . . . . . . . .. . . . .. . . . . .. .. ... . .. . . . . . . .20
2.5.1 L'Effet petit-monde. . . . . . . . . . . . . . . . .. . . . . .. . . . . . . .. . . . . . . .. . . . . . . . . . 20
2.5.2 Un coefficient de clustering (transitivité) local élevé. . . . . . . . . . … . . . .. . . . . .21
2.5.3 Clusterisation.. . . .. . . ... . . .. .. . . . . . . . . . . . . . .. . . . . .. . . . . .. . . . .. . . .. .. 21
2.6 Classification des approches de détection de communautés . . . . . .. .. . . . . . . … . 22
2.6.1 Les approches statiques sans recouvrement. . . . . .. . . . . . .. . . .. . . . . . . . . . .22
2.6.1.1 Les approches hiérarchiques .. . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . .22
A. Approches hiérarchiques ascendantes (agglomératives)…. . . . . .. ... . . . . .22
B. Approches hiérarchiques descendantes (divisives)…….. . . . . . . . . . . . . . .24
2.6.1.2 Approches utilisant des marches aléatoires. . . . . . . . . . . .. . . . . . . . .. . . . .26
2.6.1.3 Approches spectrales . . . . .. .. . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . .27
2.6.2 Les approches statiques avec recouvrement. . . . . . . . . . . .. . . . . . . . . . . . . . . . 27
2.6.2.1 Approches basées sur des cliques. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . 27
2.6.2.2 Approches basées sur la propagation de labels. . . . . .. . . . . . . . .. . . . . . .. .28
2.6.2.3 Approches basées sur des graines. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .29
2.6.2.4 Autres approches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
2.6.3 Les approches dynamiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 31
2.6.3.1 Les approches par détections statiques successives. . . . . . . . . . . . . . . . . . .31
A Approches non recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
B Approches recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.3.2 Les approches par détections statiques informées successives. . . . . . . . . . 32
A Approches non recouvrantes. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
B Approches recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.7 Conclusion. .. . . . . . .. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. ..33
3 Contribution Et Algorithmes Etudiés
3.1 Introduction. .. . . . . . . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . 33
3.2 Détecter Communautés avec la Méthode VOS Clustering. .. … .. .. .. .. . . .. . .. ..33
3.3 Détecter les recouvrements avec la méthode de Fuzzy -K-means . . . . .. . . . . . . . 36
3.3.1 Avantages. . . . . . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . 37
3.3.2 Inconvénients. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . .38
3.4 Contribution. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . .38
3.4.1 Distances et métriques. .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . .38
3.4.1.1 Notion de distance .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . .. 38
3.4.1.2 Quelques types de distances… . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . .. . 38
3.4.1.3 Similarité… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . 41
3.5 Conclusion… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 42
4 Validation Des Résultats
4.1 Introduction… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 43
4.2 Implémentation.. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 43
4.2.1 Java.. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.2.2 NetBeans .. . . . . .. … . . .. .. . . . .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.3 Les Benchmarks de Test . . .. .. . . . .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.3.1 Benchmark du Club de Karaté Zachary. .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Benchmark du réseau social Southern Women.. . . . . . . . . . . . . . . . . . . . . . . . .44
4.4 Détection de communautés partitionnées et recouvrement. . . . . . . . . . . . . . . 44
4.4.1 Détection de communautés partitionnées.. . .. .. . . . . . . . . . .. . . . . . . . . . . . . .44
4.4.2 Détection et analyse de communautés recouvrantes. . . . . . . . . . . . . . . . . . . . . .48
4.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . ..51
Conclusion générale. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . .52
BibliographieCôte titre : MAI/0124 En ligne : https://drive.google.com/file/d/1F406BCC-asu3AvYZrfdiWgPzC0nG9kh1/view?usp=shari [...] Format de la ressource électronique : Apprentissage automatique dans les réseaux sociaux [texte imprimé] / Kebbab,naouel ; A Moussaoui, Directeur de thèse . - [S.l.] : Setif:UFA, 2016 . - 1 vol (52f.) ; 29 cm.
Langues : Français (fre)
Catégories : Thèses & Mémoires:Informatique Mots-clés : Réseaux
Systèmes Distribués
apprentissage automatique
réseaux sociauxIndex. décimale : 004 Informatique Résumé : Résumé
Dans les grands réseaux, la détection de sous-ensembles de sommets plus densément
connectés que d’autres, appelés des communautés, est un problème que l’on retrouve dans
plusieurs disciplines : Biologie (réseaux d’interactions entre protéines), Informatique
(recherche d’informations sur le Web), mais aussi, Sociologie (groupes dans des réseaux
sociaux). Ces communautés jouent un rôle important dans l’organisation ou la structuration
des réseaux.
De fait, il s’agit de déterminer des classes dans un graphe. Ce problème est donc
fortement lié à celui du partitionnement, avec la spécificité suivante : suivant l’usage que
l’on veut faire de ces communautés, les classes peuvent (doivent) être disjointes ou non. En
Biologie, où l’on analyse 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.
Ainsi, les méthodes traditionnelles en Classification peuvent être utilisées ; en
particulier 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, 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.
Cette approche originale basée sur les techniques de Data Mining pour l’extraction
des connaissances, est l’algorithme FCM (Fuzzy C-Means).
Une étude de performances, dans laquelle nos méthodes sont testés sur des différents
graphes réels atteste de leur pertinence.Note de contenu : Table des matières
Remerciements
Résumé
Table des matières
Table de figures
Introduction Générale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ..…. 1
1 Data Mining
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . 3
1.2 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Entrepôts de données . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . 4
1.4 Le Data Mining est né de . . . . . . . . . . . . . . . . . . . . . …. . . . . . . . . . . . . . . . . . . . . . . 4
1.5 Data Mining et KDD (Knowledge Data Discovery) . . . .. . . . . . . . . . . . .. . . . . . …. 5
1.6 DM : les raisons du développement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
1.7 Mise en œuvre d’un projet de DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.8 Caractérisation des méthodes de DM. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.8.1 DM : une nouvelle conception de la statistique et du rôle des modèles. . . . . . . . .6
1.8.2 Tâches du Data Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . 7
1.8.2.1 Classification. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.8.2.2 Clustering(Segmentation) . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .8
1.8.2.3 Règles d’association . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.8.2.4 Recherche de séquences. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .8
1.8.2.5 Détection de déviation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . … . . .9
1.9 Techniques et algorithmes de DM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.9.1Classification supervisé. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 10
1.9.1.1 Les arbres de décision. . . . . . . . . . . .. . . . . . . . .. . . . . . . . . . . . . . .. . . . . .10
1.9.1.2 Les réseaux de neurones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . 11
1.9.1.3 Classification bayésienne. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.9.1.4 Support Vecteurs Machine(SVM) . . . . . . . . .. .. .. .. . . . . .. .. . . . . . .. .. . . 13
1.9.1.5 k plus proches voisins. . . . .. .. . . . . . .. . . .. . . . . . .. . . . . .. . . .. . .. . . . . .. .13
1.9.2 Classification non-supervisé(Automatique). . . . . . . . . . . . . . . . . . . . . . . . . . . .14
1.9.2.1 Classification hiérarchique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
1.9.2.2 Classification par densité . . . . . . . . . . . .. . . . . . . . . … .. .. . . .. . . .. .. . . . .15
1.9.2.3 Classification par partition. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . .16
1.10 Conclusion. . . . . . . . .. . . . . .. . . . . . .. . . . . . . . . . .. . . . . . .. . . .. .. . . . . . . . .. . . 16
2 Détection De Communautés Dans Les Réseaux Sociaux
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Concepts. . . . . . . .. . .. . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2.1 Qu’est-ce qu’un réseau social. . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .17
2.2.2 Communauté . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . .. .. . . . . . 18
2.2.3 La détection de communautés. . . . .. . . . . . .. . .. . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Exemples de réseaux sociaux . . . . . . . . . . . . . .. . . . . . . . . .. .. . . .. . . . . . . . . . . . . . 18
2.3.1 Club de karaté du Zachary. .. . .. .. . . . . . . .. .. .. . .. . . .. .. . . . . .. . . . . . .. . . ... . 18
2.3.2 Le graphe de Pages Web. . . . . . . .. . . . . . . . . . . . . . .. . . . . .. . . . . . . .. . . . . . . . 19
2.4 Analyse des réseaux sociaux. . . . . . . . .. . .. . . . . . . . . . . . . . . . . . .. . . . . . . . 19
2.5 Caractéristique d’un réseau social. . . . . . . . . . .. . . . .. . . . . .. .. ... . .. . . . . . . .20
2.5.1 L'Effet petit-monde. . . . . . . . . . . . . . . . .. . . . . .. . . . . . . .. . . . . . . .. . . . . . . . . . 20
2.5.2 Un coefficient de clustering (transitivité) local élevé. . . . . . . . . . … . . . .. . . . . .21
2.5.3 Clusterisation.. . . .. . . ... . . .. .. . . . . . . . . . . . . . .. . . . . .. . . . . .. . . . .. . . .. .. 21
2.6 Classification des approches de détection de communautés . . . . . .. .. . . . . . . … . 22
2.6.1 Les approches statiques sans recouvrement. . . . . .. . . . . . .. . . .. . . . . . . . . . .22
2.6.1.1 Les approches hiérarchiques .. . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . . . . . .22
A. Approches hiérarchiques ascendantes (agglomératives)…. . . . . .. ... . . . . .22
B. Approches hiérarchiques descendantes (divisives)…….. . . . . . . . . . . . . . .24
2.6.1.2 Approches utilisant des marches aléatoires. . . . . . . . . . . .. . . . . . . . .. . . . .26
2.6.1.3 Approches spectrales . . . . .. .. . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . .27
2.6.2 Les approches statiques avec recouvrement. . . . . . . . . . . .. . . . . . . . . . . . . . . . 27
2.6.2.1 Approches basées sur des cliques. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . 27
2.6.2.2 Approches basées sur la propagation de labels. . . . . .. . . . . . . . .. . . . . . .. .28
2.6.2.3 Approches basées sur des graines. . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . .29
2.6.2.4 Autres approches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30
2.6.3 Les approches dynamiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . 31
2.6.3.1 Les approches par détections statiques successives. . . . . . . . . . . . . . . . . . .31
A Approches non recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
B Approches recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.6.3.2 Les approches par détections statiques informées successives. . . . . . . . . . 32
A Approches non recouvrantes. . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . .32
B Approches recouvrantes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.7 Conclusion. .. . . . . . .. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. ..33
3 Contribution Et Algorithmes Etudiés
3.1 Introduction. .. . . . . . . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . 33
3.2 Détecter Communautés avec la Méthode VOS Clustering. .. … .. .. .. .. . . .. . .. ..33
3.3 Détecter les recouvrements avec la méthode de Fuzzy -K-means . . . . .. . . . . . . . 36
3.3.1 Avantages. . . . . . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . 37
3.3.2 Inconvénients. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . .38
3.4 Contribution. . . . … .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . .38
3.4.1 Distances et métriques. .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . .38
3.4.1.1 Notion de distance .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . .. 38
3.4.1.2 Quelques types de distances… . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . .. . 38
3.4.1.3 Similarité… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . 41
3.5 Conclusion… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 42
4 Validation Des Résultats
4.1 Introduction… .. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 43
4.2 Implémentation.. .. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . 43
4.2.1 Java.. . .. .. . . . . .. … . . .. .. . . . .. .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.2.2 NetBeans .. . . . . .. … . . .. .. . . . .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.3 Les Benchmarks de Test . . .. .. . . . .. . . .. . . .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . .43
4.3.1 Benchmark du Club de Karaté Zachary. .. . .. .. . . . . . . . . . . . . . . . . . . . . . . . . 44
4.3.2 Benchmark du réseau social Southern Women.. . . . . . . . . . . . . . . . . . . . . . . . .44
4.4 Détection de communautés partitionnées et recouvrement. . . . . . . . . . . . . . . 44
4.4.1 Détection de communautés partitionnées.. . .. .. . . . . . . . . . .. . . . . . . . . . . . . .44
4.4.2 Détection et analyse de communautés recouvrantes. . . . . . . . . . . . . . . . . . . . . .48
4.5 Conclusion. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. .. . . . . . ..51
Conclusion générale. . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . .52
BibliographieCôte titre : MAI/0124 En ligne : https://drive.google.com/file/d/1F406BCC-asu3AvYZrfdiWgPzC0nG9kh1/view?usp=shari [...] Format de la ressource électronique : Exemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité MAI/0124 MAI/0124 Mémoire Bibliothéque des sciences Français Disponible
Disponible