Table des matières
Résumé 3
Summary 4
Table des matières 5
Avant-propos 8
I. La solitude du chercheur d'informations 8
II. L'observation d'internautes en recherche d'informations
10
III. Pourquoi briser la solitude du chercheur d'informations '
17
IV. Comment briser la solitude du chercheur d'informations '
18
V. Dernière justification... 22
Introduction générale 23
I. Contexte et motivation 23
II. Approche et principaux objectifs 24
III. Plan du mémoire 25
Première Partie - Définitions et
état de l'art 26
Chapitre 1 - État de l'art, notions,
définitions et vocabulaire sur les graphes 27
1.1 Introduction 27
1.2 Historique 28
1.2.1 Le problème 28
1.2.2 La réponse par le graphe 28
1.3 Notions et définitions 30
1.4 Grands graphes de terrain 39
1.4.1 Définition 39
1.4.2 Caractéristiques 40
1.4.3 Contexte 41
1.4.4 Des petits mondes ou la légende des six
poignées de mains 42
1.5 Les communautés 43
1.5.1 Définition et choix de la terminologie : clusters,
communautés ou agrégats ? 43
1.5.2 Recherche et détection de communautés dans
les graphes 46
1.6 Conclusion 47
1.6.1 Vocabulaire et terminologie 47
1.6.2 Caractéristiques et valeurs 47
Chapitre 2 - Les algorithmes de création de
communautés 49
2.1 Introduction 49
2.2 Les partitions ou communautés sans recouvrement 50
2.2.1 Les algorithmes séparatistes 51
2.2.2 Les algorithmes de scission 53
2.2.3 Les algorithmes de recherche de zones de forte
modularité 54
2.3 Les différentes méthodes de recherche de
communautés avec recouvrement 55
2.3.1 Méthodes de recherche de formes : la percolation de
cliques 56
2.3.2 Les méthodes en plusieurs phases 58
2.3.3 Les méthodes par déplacement d'objets 64
2.3.4 Méthodes modifiées pour permettre le
recouvrement 71
2.4 Les méthodes de validation des communautés
74
2.4.1 Validation qualitative 74
2.4.2 Évaluation de la complexité 78
2.5 Synthèse 79
2.5.1 Caractéristiques importantes 79
2.5.2 Méthodes créant des communautés sans
recouvrement 82
2.5.3 Méthodes créant des communautés avec
recouvrement 83
2.5.1 Conclusion 84
2.6 Conclusion 85
6
Deuxième Partie - Nos propositions pour la
création d'agrégats par rigidification et
enrichissement 87
Chapitre 3 - Les méthodes d'agrégations
proposées 89
3.1 Introduction 89
3.2 Méthode 1 : Détection de cliques 90
3.2.1 La clique ou une densité maximale 90
3.2.2 Mécanisme de regroupement des mots-clés en
cliques 91
3.3 Méthode 2 : Rigidification Simple 92
3.3.1 Définition des problèmes de satisfaction
de contraintes géométriques G.C.S.P (Geometric Constraint
Satisfaction Problem) 93
3.3.2 Présentation de HLS 93
3.3.3 Les étapes de la méthode HLS 94
3.3.4 Implantation et adaptation de la méthode HLS 94
3.4 Méthode 3 : Rigidification Régulée
100
3.4.1 Dans quel but une nouvelle méthode
améliorée ? 101
3.4.2 Présentation de l'algorithme « Rigidification
Régulée » 106
3.5 Méthode 4 : Méthode d'enrichissement
d'agrégats par gravité 113
3.5.1 Les objectifs d'une méthode d'enrichissement des
agrégats. 114
3.5.2 Présentation de la méthode d'Enrichissements
par gravité 116
3.6 Conclusion 118
Chapitre 4. - Expérimentations, validations
sémantiques et résultats de mesure 121
4.1 Introduction 121
4.2 Présentation des réseaux testés 121
4.2.1 Les réseaux AOL 122
4.2.2 Les réseaux eDonkey 125
4.2.3 TREC-Eval 74
4.3 Les méthodes de validation sémantique 128
4.3.1 Méthode MCCVS ou « Méthode Comparative
de Coefficient de Validation Sémantique » 128
4.3.2 Méthode TREC-Eval : enrichissement de requêtes
136
4.3.3 Méthode MCCDR ou « Méthode de
Comparaison de Cohérence de Documents Retournés » 139
4.1.1 Conclusion sur les méthodes de validation 149
4.4 Résultats des regroupements et validation
sémantique 151
4.4.1 Agrégation par regroupement en cliques sur
réseau AOL-17/04/2006 et validation manuelle 151
| 
