WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain


par Christian Belbèze
Université Toulouse 1 Capitole - Doctorat en informatique 2012
  

précédent sommaire suivant

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

précédent sommaire suivant







Rassembler les contraires c est creer l harmonie