Nouveaux algorithmes pour le calcul de centralité dans les graphes de documents

Table des matières

Introduction
Motivations
Les graphes de documents
Publications dans le cadre de la thèse
Organisation de la thèse
Chapitre 1 Etat de l’art sur le calcul de centralité
1.1 La notion de centralité dans les graphes
1.2 Mesures de centralité issues de l’Analyse des Réseaux Sociaux (ARS)
1.2.1 Centralité de degré
1.2.2 Centralité de proximité
1.2.3 Centralité d’intermédiarité
1.2.4 Centralité spectrale
1.2.5 Limites des mesures de centralité issues de l’ARS
1.3 Mesures de centralité issues de la Recherche d’Information (RI)
1.3.1 PageRank
1.3.2 HITS
1.3.3 Salsa
1.3.4 HubAvg
1.4 Bilan
Chapitre 2 Nouveaux algorithmes pour le calcul de centralité dans les graphes de documents
2.1 L’effet TKC (Tightly Knit Community)
2.2 L’algorithme MHITS (Multi-HITS)
2.2.1 Principe
2.2.2 Détails de l’algorithme
2.2.3 Exemples jouets
2.2.4 Convergence de l’algorithme
2.3 L’algorithme NHITS (Non-negative HITS)
2.3.1 HITS et la décomposition en valeurs singulières
2.3.2 Décomposition de la matrice d’adjacence en matrices non négatives
2.3.3 Détails de l’algorithme
2.3.4 Résultats avec les graphes jouets
2.3.5 Effet du nombre de dimensions et convergence de l’algorithme
2.4 L’algorithme DocRank
2.4.1 Principe
2.4.2 Distributions stationnaires
2.4.3 Détails de l’algorithme
2.4.4 Exemples jouets
2.5 Environnement d’expérimentation
2.5.1 Graphes de documents utilisés
2.5.2 Mesures d’évaluation
2.5.3 Algorithmes comparés
2.6 Résultats expérimentaux
2.6.1 Evaluation de la qualité du classement
2.6.2 Evaluation de la diversité thématique
2.7 Bilan
Chapitre 3 Etat de l’art sur l’Identification de Structures de Communautés (ISC)
3.1 Notion de communauté et problème de l’ISC
3.1.1 Définitions basées sur la connectivité des sommets
3.1.2 Définitions basées sur la similarité des sommets
3.1.3 Définitions basées sur une fonction de qualité
3.1.4 L’identification de structures de communautés
3.2 Approches non génératives pour l’ISC
3.2.1 Approches basées sur le clustering par partitionnement
3.2.2 Approches basées sur le clustering hiérarchique ascendant
3.2.3 Approches basées sur le clustering hiérarchique descendant
3.2.4 Approches basées sur le partitionnement de graphes
3.2.5 Autres approches
3.3 Approches génératives pour l’ISC
3.3.1 Introduction aux modèles génératifs
3.3.2 Approches basées sur le modèle de mélange de multinomiales
3.3.3 Approches basées sur le modèle PLSA
3.3.4 Approches basées sur le modèle SBM
3.4 Synthèse des approches présentées et leur adéquation à l’analyse des graphes de documents
Chapitre 4 Des modèles génératifs pour l’identification de structures de communautés dans les graphes de documents
4.1 Le modèle SPCE (Smoothed Probabilistic Community Explorer)
4.1.1 Processus génératif
4.1.2 Estimation des paramètres
4.2 Mise en œuvre du modèle SPCE
4.2.1 Initialisation de l’algorithme EM
4.2.2 Estimation des paramètres de lissage
4.2.3 Calcul du nombre de communautés
4.3 Evaluation expérimentale du modèle SPCE
4.3.1 Evaluation de l’ISC
4.3.2 Effet des paramètres de lissage
4.3.3 Evaluation de la robustesse à la faible densité
4.3.4 Evaluation de la convergence
4.3.5 Evaluation du calcul du nombre de communautés
4.4 SPCE-PLSA : un modèle hybride pour l’analyse des liens et des contenus
4.4.1 Processus génératif
4.4.2 Estimation des paramètres
4.4.3 Mise en œuvre du modèle
4.4.4 Résultats expérimentaux
4.5 Bilan
Conclusion