Soutenance mémoire
Les graphes de documents possèdent des particularités qui ont nécessité le développement de mesures de centralité spécifiques. Ces mesures ont été principalement proposées en recherche d’information (RI) dans le but d’améliorer la performance des moteurs de recherche sur le web. Nous décrivons quelques uns des algorithmes les plus emblématiques pour le calcul de degrés d’importance dans les graphes de documents notamment l’algorithme PageRank de Brin et Page et l’algorithme HITS de Kleinberg. Les avantages et inconvénients de chacun des algorithmes sont également exposés en insistant sur un problème récurrent à savoir l’effet TKC (Tightly Knit Community) dont souffre un grand nombre de ces approches.
La notion de centralité dans les graphes
Dans le cadre de l’analyse des réseaux sociaux, les chercheurs ont remarqué que certains acteurs jouent un rôle plus « important » que d’autres. Certaines personnes avaient par exemple beaucoup de contacts au sein du réseau alors que d’autres personnes n’en avaient que très peu. Ces personnes occupent en fait une position stratégique (ou avantageuse) au sein du réseau social ; suivant les cas, ces personnes peuvent être plus influentes ou avoir une plus grande notoriété. Ce phénomène n’est pas propre aux réseaux sociaux puisqu’on le retrouve dans beaucoup d’autres types de graphes. Par exemple, dans les réseaux de communication, certains nœuds jouent un rôle très important dans la communication entre les nœuds alors que d’autres nœuds n’ont aucune influence sur le réseau. Ce phénomène s’explique par la nature de ces réseaux qui sont des réseaux complexes et dont la distribution des nœuds suit une loi de puissance [Caldarelli 07]. Cette loi de probabilité signifie qu’un petit nombre de nœuds possède beaucoup de connexions (i.e. de liens) alors qu’un grand nombre de nœuds possède peu de liens avec les autres nœuds du réseau. En d’autres termes, les nœuds n’ont pas les mêmes rôles au sein du réseau.
Dans le but de quantifier cette notion d’importance d’un nœud dans un graphe, les chercheurs ont proposé plusieurs définitions connues sous le nom de mesures de centralité [Koschützki et al. 05]. En effet, l’identification des nœuds centraux dans un graphe représente un enjeu important dans plusieurs domaines. En reprenant l’exemple des réseaux de communication, le fait de connaître les nœuds importants permet d’adopter des stratégies afin de mieux protéger ces nœuds qui jouent un rôle essentiel dans la communication au sein du réseau. Si l’on considère à titre d’exemple le réseau de communication de la figure 1.1, on remarque que si le nœud B tombe en panne, la communication entre les différents nœuds ne sera pas affectée. Par contre, si le nœud A tombe en panne, cela engendrerait un grand problème de communication puisque tous les nœuds se retrouveront isolés.
En recherche d’information, le classement (ou « ranking ») des résultats est basé non seulement sur une mesure de similarité entre la requête utilisateur et les documents mais aussi sur le degré d’importance (ou d’autorité) d’un document dans le graphe de citations.
Lors de l’étude de la notion de centralité, il est important de distinguer le cas des graphes orientés du cas des graphes non-orientés. Dans les graphes orientés, les nœuds possèdent deux types de liens, à savoir des liens entrants et des liens sortants. Pour une définition donnée de la notion de centralité, chaque nœud aura alors deux mesures d’importance : une mesure relative à ses liens sortants, appelée mesure de centralité, d’influence, d’hubité ou de centralité sortante, et une autre mesure relative à ses liens entrants, appelée mesure de prestige, de popularité, d’autorité ou de centralité entrante [Wasserman and Faust 94]. Dans un graphe non orienté, chaque nœud possède un seul type de liens ou de relations avec les autres nœuds. Chaque nœud possède alors une seule mesure d’importance (correspondant à une définition précise) appelée mesure de centralité [Wasserman and Faust 94].
Mesures de centralité issues de l’Analyse des Réseaux Sociaux (ARS)
Le calcul de centralité est depuis plusieurs décennies une problématique importante dans le domaine de l’analyse des réseaux sociaux [Wasserman and Faust 94]. La centralité est une notion qui permet de rendre compte de la popularité ou visibilité d’un acteur au sein d’un groupe. L’article « Centrality in social networks: Conceptual clarification [Freeman 79] » de Freeman représente sans doute l’une des contributions les plus importantes dans le domaine de l’analyse des réseaux sociaux. Dans son article, Freeman propose trois définitions formelles du concept de centralité que nous présentons ci-dessous. Nous présentons également une quatrième définition introduite par Bonacich qui est à la base d’un grand nombre de mesures de centralité dans les graphes de documents.
Centralité de degré
La centralité de degré [Freeman 79] représente la forme la plus simple et la plus intuitive de la notion de centralité. Elle est basée sur l’idée que l’importance d’un individu au sein d’un groupe dépend du nombre total de personnes qu’il connaît ou avec lesquelles il interagit directement. Selon cette mesure, déterminer l’importance d’un nœud dans un graphe revient donc à calculer le nombre de ses sommets voisins, ou de manière équivalente, à calculer le nombre de liens qui lui sont incidents. En théorie des graphes, ce nombre est appelé degré du nœud, d’où l’appellation de centralité de degré.
La centralité de degré est aussi appelée mesure de centralité locale [Scott 00] car elle ne prend pas en compte la structure globale du graphe et n’est calculée qu’à partir du voisinage immédiat d’un sommet. Bien qu’elle soit pertinente dans certaines situations, la centralité de degré s’avère être peu informative dans d’autres cas, comme par exemple pour l’analyse des graphes de pages web [Kleinberg 99a]. Les mesures que nous présentons dans la suite sont toutes des mesures de centralité globales.
Centralité de proximité
La centralité de proximité [Freeman 79] est une mesure de centralité globale basée sur l’intuition qu’un nœud occupe une position stratégique (ou avantageuse) dans un graphe s’il est globalement proche des autres nœuds de ce graphe. Par exemple dans un réseau social, cette mesure correspond à l’idée qu’un acteur est important s’il est capable de contacter facilement un grand nombre d’acteurs avec un minimum d’effort (l’effort ici est relatif à la taille des chemins). En pratique, la centralité de proximité d’un nœud est obtenue en calculant sa proximité moyenne vis-à-vis des autres nœuds du graphe.
Centralité d’intermédiarité
La centralité d’intermédiarité [Freeman 79] est une autre mesure de centralité globale proposée par Freeman. L’intuition de cette mesure est que, dans un graphe, un nœud est d’autant plus important qu’il est nécessaire de le traverser pour aller d’un nœud quelconque à un autre. Plus précisément, un sommet ayant une forte centralité d’intermédiarité est un sommet par lequel passe un grand nombre de chemins géodésiques (i.e. chemins les plus courts) dans le graphe. Dans un réseau social, un acteur ayant une forte centralité d’intermédiarité est un sommet tel qu’un grand nombre d’interactions entre des sommets non adjacents dépend de lui [Borgatti and Everett 06]. Dans un réseau de communication, la centralité d’intermédiarité d’un nœud peut être considérée comme la probabilité qu’une information transmise entre deux nœuds passe par ce nœud intermédiaire [Borgatti and Everett 06].
|
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
