Métrologie des graphes de terrain

De la théorie des graphes à l’étude des graphes de terrain

   Les graphes sont des outils de modélisation et de raisonnement puissants et néanmoins simples dans leur formalisation. Le développement des théories mathématiques sous-jacentes est relativement ancien, il connaît cependant un renouveau important depuis environ une quinzaine d’années. On indique en général que l’étude des graphes, comme objets mathématiques, commence en 1735 quand Leonhard Euler présente à l’académie de Saint Pétersbourg le problème des sept ponts de Königsberg (l’article a ensuite été publié en 1741, [Euler, 1741]). Ce problème consiste à trouver un chemin qui permette de revenir au lieu de départ après être passé une seule fois par chacun des sept ponts de la ville. Ce type de chemin dans un graphe est maintenant nommé chemin eulérien. Depuis ce premier travail s’est développée une branche des mathématiques discrètes : la théorie des graphes [Berge, 1970]. Cette théorie s’intéresse à un certain nombre de questions pratiques, par exemple : quel est le plus court chemin reliant deux sommets ? quelle est la taille du plus court chemin passant par tous les sommets ? comment, avec le moins de couleurs possibles, colorier chaque sommet d’un graphe de façon à ce que deux sommets adjacents soient toujours de couleurs différentes ? connaissant la capacité de chaque arête, quel est le flux maximal possible entre deux sommets ? ou encore, comment séparer les sommets d’un graphe en deux parties de même taille en retirant un nombre minimal d’arêtes entre ces parties ? Tous ces développements ont eu, et ont encore, d’importantes applications en chimie [Trinajstić, 1983; Faulon, 1998], en physique [Harary, 1967], en ingénierie (électronique, télécommunication, etc.) [Ohlrich et al., 1993; Kahng et al., 2011] et en informatique [Bollobás, 1998; Diestel, 2000]. Il convient aussi de noter que les systèmes de représentation des connaissances constituent une autre application importante de la théorie des graphes. Nous pouvons citer le formalisme des graphes conceptuels [Chein et Mugnier, 2008], ou encore celui des réseaux bayésiens [Naïm et al., 2011]. À partir des années 1920, et parallèlement au développement de la théorie des graphes, un autre usage des graphes se développe en sciences humaines par l’analyse des réseaux sociaux . En effet, bien que cette discipline se soit fortement développée depuis moins d’une trentaine d’années, les premiers travaux datent de la première moitié du XXème siècle, voir [Freeman, 1996], [Wasserman et Faust, 1994, chap. 1.2] et [Carrington et al., 2005, chap. 1]. L’analyse des réseaux sociaux, bien que s’appuyant en partie sur la théorie des graphes, pose des problèmes différents de ceux étudiés classiquement dans cette discipline. Par exemple : quels sont les acteurs (i.e. sommets) centraux dans un groupe social ? quelles sont les différentes communautés ? comment modéliser tel type de structure sociale ? Les travaux d’analyse des réseaux sociaux s’appuient donc aussi fortement sur les statistiques et la théorie des probabilités [Wasserman et Faust, 1994; Carrington et al., 2005]. De plus il faut remarquer que les graphes étudiés proviennent de relevés « de terrain ». Dans ce contexte, plusieurs découvertes faites il y a un peu plus d’une décennie ont engendré un intérêt nouveau à l’étude des graphes au sein de différentes communautés scientifiques. Watts et Strogatz [1998] ainsi que Barabási et Albert [1999] ont montré que des graphes issus de systèmes réels variés (interaction de protéines, liens hypertextes, réseaux sociaux, etc.) possèdent des propriétés non-triviales communes. Dans ces graphes, deux sommets sont toujours reliés par un chemin de longueur faible (on parle du phénomène de petit monde). Aussi, alors qu’une large majorité des sommets ont peu de voisins, un certain nombre de sommets sont très fortement liés. Nous présentons plus en détails ces propriétés en section 1.3. Cela a donné un nouvel intérêt à l’étude et à l’utilisation des graphes comme outils de modélisation et a engendré un nombre considérable de travaux qui en sortant du champ de la théorie des graphes classique tendent à créer une nouvelle discipline. On parle de « network science » ou de « network theory » (science ou théorie des réseaux, en français). Les graphes, issus de systèmes réels et possédant des propriétés non-triviales particulières, sont souvent nommés complex networks  dans la littérature anglophone (i.e. réseaux complexes). On parle parfois aussi de grands réseaux d’interaction. Pour notre part, nous préférons le terme réseaux de terrain ou graphes de terrain , pour bien souligner le fait que ces graphes sont issus de données « réelles », de données de « terrain ». Nous parlerons donc de l’étude de graphes de terrain, plutôt que de science des réseaux. Notons que beaucoup de travaux en analyse des réseaux sociaux sont précurseurs de cette nouvelle discipline, tant par les problèmes abordés, les méthodes utilisées, que par les objets d’étude (graphes issus de systèmes réels). D’une autre manière, cette nouvelle discipline hérite aussi directement des travaux de la théorie des graphes s’intéressant aux graphes aléatoires, en particulier les travaux d’Erdős et Rényi [1959, 1960] et ceux qui ont suivi . L’étude des graphes de terrain ou la science des réseaux est donc la discipline qui s’intéresse à développer des outils et méthodes tâchant de modéliser et d’exploiter des données ou systèmes réels prenant la forme de graphes. La simplicité de cette définition indique bien le caractère très général de cette discipline. Effectivement, malgré sa jeunesse, une riche variété de travaux la compose (ce qui ne rend pas évident le dessin de frontières nettes). De plus ce domaine d’étude est pluridisciplinaire à plusieurs niveaux : tout d’abord du fait des applications (en sociologie, biologie, ingénierie, recherche d’information, traitement automatique du langage naturel, etc.), et ensuite du fait de l’origine des chercheurs s’y intéressant (mathématiques discrètes et théorie des graphes, étude des réseaux sociaux, physique statistique, analyse de données, intelligence artificielle, systèmes multi-agents, systèmes complexes, etc.). Notons, pour finir ce rapide historique, que « l’écosystème » scientifique de cette nouvelle discipline commence à se structurer. Au niveau international, on peut citer la conférence annuelle NetSci  qui existe depuis 2006. Aussi, en France la conférence MARAMI existe maintenant depuis 2010.

Chemins et composantes connexes

   Un chemin entre un sommet u et un sommet v est une séquence de sommets démarrant par u et terminant par v et telle que chaque sommet est adjacent avec son suivant. La longueur (ou taille) d’un chemin est le nombre d’arêtes le composant, c’est-à-dire la longueur de la séquence moins un. On note hu, x1, . . . , xk−1, vi un chemin de longueur k allant du sommet u au sommet v, les sommets intermédiaires étant notés x1, . . ., xk−1. On appelle parfois chaîne un chemin sur un graphe nondirigé, en réservant le terme de chemin pour les graphes dirigés. Dans la suite nous utiliserons uniquement le terme de chemin, le contexte permettant de désambiguïser. Sur un graphe dirigé un chemin est orienté, ses arcs doivent être orientés dans le même sens que le chemin. Si le point de départ u et d’arrivée v d’un chemin (ou d’une chaîne) se confondent, alors on parle de cycle. Ainsi une boucle est un cycle de longueur 1. Deux sommets sont dits connectés s’il existe un chemin de longueur quelconque entre eux. À l’inverse deux sommets sont déconnectés s’il n’existe aucun chemin les reliant. Deux sous-ensembles de sommets A, B sont déconnectés si chaque sommet de A est déconnecté de tous les sommets de B. Dans un graphe G = (V, E), un sous-ensemble de sommets V 0 ⊂ V est une composante connexe s’il existe un chemin reliant chaque paire de sommets de V0. Un graphe G = (V, E) est dit connexe si V est une composante connexe. Dans un graphe dirigé, on parle de composante fortement connexe si l’orientation des arcs est prise en compte. C’est-à-dire une composante fortement connexe est un ensemble de sommets reliés deux à deux et dans les deux sens par des chemins orientés. À l’inverse, on parle de composante faiblement connexe si l’orientation des arcs est ignorée ; il suffit qu’il existe un chemin de u à v (sans forcément qu’il existe de chemin « retour » de v à u) pour que u et v appartiennent à la même composante faiblement connexe. Une composante connexe est maximale si on ne peut lui ajouter de sommet sans qu’elle ne perdre sa connexité. Souvent dans la littérature on utilise simplement « composante connexe » pour parler des composantes connexes maximales. Nous ferons cette approximation lexicale dans la suite de ce rapport.

Le phénomène de petit monde

   L’une des caractéristiques en apparence la plus surprenante des graphes de terrain est le phénomène de petit monde : la longueur du plus court chemin existant entre deux sommets est toujours « faible », même dans de très grands réseaux. Ce phénomène a été découvert d’abord sur les réseaux sociaux. Il fut expérimenté pour la première fois par le sociologue Stanley Milgram en 1967, [Milgram, 1967]. Milgram demanda à 60 personnes du Nebraska (États-Unis) de faire parvenir une lettre à une personne vivant dans le Massachusetts. Seulement, bien que connaissant l’adresse du destinataire, les participants ne pouvaient passer la lettre que, de main à main, à des personnes de leur connaissance. Les lettres qui arrivèrent à destination ne passèrent en moyenne que par six personnes . Mais ce n’est pas cette caractéristique seule qui est remarquable. En effet, les graphes aléatoires de type Erdős et Rényi [1959] présentent eux aussi une faible longueur moyenne des plus courts chemins. C’est la combinaison d’une faible longueur moyenne des plus courts chemins (l faible) et d’un fort coefficient de transitivité (c fort) qui est remarquable dans les graphes réels. C’est ce que Watts et Strogatz ont montré dans leur article de 1998. Les graphes réels se situent ainsi entre des graphes artificiels en « grilles » (fort c et fort l) et les graphes aléatoires (faible c et faible l). Watts et Strogatz [1998] montrent que ce phénomène se vérifie sur des réseaux réels de différentes origines (pas seulement sur les réseaux sociaux).

Cluster Graph Model, CGM

   Nous proposons d’appeler CGM (pour Cluster Graph Model) le modèle consistant à construire un graphe à partir de k groupes de r sommets chacun, tel que les arêtes soient aléatoires mais avec différentes probabilités à l’intérieur ou entre les groupes. Une arête entre deux sommets du même groupe existe avec une probabilité µintra, et avec une probabilité µinter entre des sommets de groupes différents. Les deux graphes ont été construits avec k = 5, r = 50. Pour CGMpd on a µintra = 0.15 et µinter = 0.01, alors que pour CGMtd µintra = 0.50 et µinter = 0.02. CGMtd est donc plus dense, et avec des clusters plus lisibles que CGMpd.

Similarité binaire, différents cas de figure

   Les deux cas problématiques soulevés en section 3.2.2 résultent du fait que les arêtes sont considérées indépendamment les unes des autres. En effet, GED suppose qu’un graphe n’est qu’un ensemble de jugements binaires indépendants : soit deux sommets sont en relation, soit ils ne le sont pas. Or, comme nous l’avons vu en sous section 3.2.2, deux sommets peuvent être proches sans être adjacents. Intuitivement, s’il existe beaucoup de chemins courts entre deux sommets, la situation n’est pas la même que s’il n’existe que peu de chemins (longs) entre ces sommets. Pourtant ces deux situations sont considérées comme équivalentes avec une mesure de type GED. Pour comprendre ces différents cas, supposons que l’on dispose d’une mesure binaire évaluant si deux sommets sont « proches » (i.e. similaires) d’après la topologie du graphe, et ce indépendamment du fait qu’ils soient adjacents ou non. Pour chaque paire de sommets, quatre cas sont possibles :
• adjacente et similaire (on note « 11 »),
• adjacente mais non-similaire (« 10 »),
• non-adjacente mais similaire (« 01 »),
• non-adjacente et non-similaire (« 00 »).
On comprend que les situations qui posaient problème jusque là correspondent au cas où une paire est adjacente (et a priori similaire) dans un graphe et non-adjacente mais similaire dans l’autre, et au cas où une paire est non-adjacente (et a priori non-similaire) dans un graphe et adjacente mais non-similaire dans l’autre. Les tableaux 3.1 montrent le changement de perspective qui s’opère lorsque l’on considère une similarité binaire, en plus de la notion d’adjacence. Quand on ne considère que l’adjacence, le tableau 3.1a présente les quatre cas possibles pour une paire donnée. Le tableau 3.1b présente les seize cas existant lorsque l’on considère, en plus, une telle similarité binaire. Sur le tableau 3.1a les interprétations (ok = accord, ko = désaccord) des quatre cas sont peu discutables. Par contre, pour évaluer les seize cas du tableau 3.1b des choix doivent être faits. Les qualifications présentées correspondent aux choix suivants :
• priorité de l’adjacence sur la similarité,
• un conflit sur l’adjacence est « résolu » s’il n’y a pas de conflit sur la similarité. Une façon de comprendre ces choix est de considérer que la similarité vient soit confirmer soit mettre en doute l’adjacence. Ainsi on a pour une paire :
• adjacente mais non-similaire (10) : doute sur l’adjacence (noté 1?),
• non-adjacente mais similaire (01) : doute sur la non-adjacence (0?),
• adjacente et similaire (11) : certitude sur l’adjacence (1!),
• non-adjacente et non-similaire (00) : certitude sur la non adjacence (0!).
Ainsi, tant qu’une arête est présente (ou absente) dans les deux graphes, peu importe si il y a un doute ou non, il n’y a pas de conflit (ok+ ou ok−). Aussi lors d’un conflit

Table des matières

1 Introduction 
1.1 De la théorie des graphes à l’étude des graphes de terrain
1.2 Notions de théorie des graphes, notations
1.2.1 Graphes
1.2.2 Graphes dirigés, graphes pondérés et graphes bipartis
1.2.3 Représentations matricielles usuelles
1.2.4 Graphes complets, cliques et bicliques
1.2.5 Chemins et composantes connexes
1.2.6 Graphes aléatoires et graphes réguliers
1.2.7 Propriétés structurelles
1.3 Propriétés non triviales communes
1.3.1 Le phénomène de petit monde
1.3.2 Distribution des degrés en loi de puissance
1.3.3 Plusieurs familles de graphes de terrains ?
1.4 Conclusion du chapitre
I Marches aléatoires courtes, application à différents problèmes de l’étude des graphes de terrain 
2 Similarités entre sommets 
2.1 Introduction
2.2 Proposition d’une mesure normalisée
2.2.1 Marches aléatoires en temps courts
2.2.2 Mesure de confluence
2.3 État de l’art des mesures de similarité entre sommets
2.3.1 Mesures locales
2.3.2 Mesures globales
2.3.3 Mesures « semi-globales »
2.4 Comparaison expérimentale
2.4.1 Mise en place expérimentale
2.4.2 Corrélation entre les méthodes
2.4.3 Comparaison sur des graphes aléatoires Erdős-Rényi
2.4.4 Comparaison sur des graphes simples comportant des clusters
2.4.5 Comparaison sur un graphe de terrain
2.4.6 Conclusion
2.5 Conclusion du chapitre
3 Comparaison robuste de graphes 
3.1 Introduction
3.2 Comparaison de graphes ayant les mêmes sommets
3.2.1 Distance d’édition entre graphes (GED)
3.2.2 Structures identiques, pourtant sans « atome » commun
3.2.3 De l’isomorphisme de graphes aux distances d’édition
3.3 Proposition d’une mesure de comparaison robuste
3.3.1 Similarité binaire, différents cas de figure
3.3.2 Similarité continue, généralisation de GED
3.3.3 Choix de la similarité ∆
3.3.4 Évaluation
3.4 Fusion de graphes de terrain
3.5 Application à la comparaison de ressources lexicales
3.5.1 Introduction des ressources comparées
3.5.2 Analyse des comparaisons
3.6 Conclusion du chapitre
4 Enrichissement semi-automatique de réseaux lexicaux 
4.1 Ressources lexicales, construction et évaluation
4.1.1 Méthodes de construction de ressources lexicales
4.1.2 Évaluation des ressources lexicales
4.2 Édition collaborative par les foules
4.2.1 Plusieurs modèles
4.2.2 Le cas de Wiktionary
4.3 Enrichissement semi-automatique
4.3.1 Modèle de graphes bipartis pondérés
4.3.2 Calcul de similarités, calcul de candidats
4.3.3 Évaluation
4.4 Une implémentation fonctionnelle : le système Wisigoth
4.5 Conclusion du chapitre
II Clustering de graphe biparti, théories et applications
5 Clustering de graphe biparti 
5.1 Différentes familles d’approches
5.1.1 Partitionnement de graphe biparti
5.1.2 Bi-clustering
5.1.3 Détection de communautés sur un graphe biparti
5.1.4 Analyse formelle de concepts
5.1.5 Recherche d’itemsets fréquents
5.2 De l’analyse formelle de concepts au clustering de graphe biparti
5.2.1 AFC, extension possibiliste
5.2.2 Traduction en théorie des graphes
5.2.3 Conclusion : vers deux types de clustering ?
5.3 Partitionnement des objets, en passant par les concepts
5.3.1 Clustering du graphe objets-concepts
5.3.2 Étiquetage des clusters
5.3.3 Évaluation
5.3.4 Conclusions et perspectives
5.4 Pré-traitement par marches aléatoires
5.4.1 Généralisations de l’AFC sur données pondérées ou incomplètes
5.4.2 Filtrage et binarisation d’un graphe biparti éventuellement
pondéré
5.4.3 Évaluation
5.4.4 Conclusion et perspectives
5.5 Conclusion du chapitre .
6 Application à l’organisation des résultats d’une recherche d’information 
6.1 Introduction, clustering de graphe documents-termes
6.2 État de l’art : le clustering appliqué à la recherche d’information
6.3 Implémentation logicielle d’une chaîne de traitement modulable (Kodex)
6.3.1 Objectifs, motivations et choix techniques
6.3.2 Types de données principaux
6.3.3 Chaînes de traitement, chaînes de composants
6.3.4 Gestion des options des composants
6.3.5 Configuration d’une chaîne de traitement en ligne
6.3.6 Analyse des documents hors-ligne
6.4 Évaluation sur une collection de deux millions de documents
6.4.1 Collection et jeu d’évaluation
6.4.2 Configuration de Kodex
6.4.3 Évaluation
6.4.4 Conclusions et perspectives
6.5 Deux applications de Kodex
6.5.1 Application sur l’API de recherche du Guardian
6.5.2 Application sur l’API de recherche de DBLP
6.6 Conclusions du chapitre 6
Conclusion
Bibliographie

Télécharger le rapport complet