COMPARAISON DE GRANDS GRAPHESApplication à la recherche de réseaux de sociabilités paysannes au Moyen-Age – GRAPHES-COMP

L'objectif de ce projet est de concevoir et implémenter des méthodes mathématiques de comparaisons de graphes, efficaces pour pouvoir être utilisées pour des grands graphes. Par grands graphes, nous faisons référence ici à des graphes d'au moins plusieurs centaines de sommets, ampleur que l'on trouve couramment dans la pratique, que l'on travaille sur des molécules chimiques, des réseaux de neurones réels, des réseaux sociaux, de liens hypertextes, ou encore en reconnaissance d'image. Pour comprendre l'intérêt du travail, reprenons ces exemples pour en tirer quelques remarques : deux protéines chimiques qui ont la même structure encodent probablement la même fonction; l'anatomie des réseaux neuronaux corticaux révèle certaines de leurs propriétés fonctionnelles; il est plus facile de bloquer la propagation d'un virus lorsqu'on connaît l'architecture du réseaux dans lequel il évolue; l'amélioration des moteurs de recherche passera peut-être par des algorithmes qui identifieront les « bonnes » pages qui correspondent à une structure particulière; l'étude d'une image peut passer par l'analyse du graphe de ses régions. On saisit alors l'importance pour l'expert de chacun de ces domaines de pouvoir analyser et « comprendre » la structure du réseau auquel il est confronté. Si le mathématicien doit s'emparer du sujet, il simplifiera ce réseau en un graphe, éventuellement pondéré ou orienté et y cherchera des symétries ou des motifs particuliers. Les symétries sont trouvées en comparant le graphe à lui-même et les motifs en le comparant bien sûr à des motifs prédéfinis. La comparaison de graphes devient donc un maillon essentiel dans un processus d'analyse de la structure d'un graphe. - Nous proposons 3 approches concurrentes et complémentaires pour comparer deux graphes : - 1. L'ensemble des n sommets du graphe est muni d'un indice de similarité. Pour deux sommets quelconques du graphe on peut : a) comparer directement les voisinages b) comparer la structure de ces voisinages. Cet ensemble métrique peut ensuite être plongé dans un espace euclidien dont la dimension est suffisamment faible pour que le nuage de points obtenu soit aisément étudiable avec des techniques d'analyse des données. Il reste alors à comparer les nuages de points obtenus pour chacun des deux graphes à comparer. - 2. On prend ici le contre-pied du 1. en plongeant les sommets du graphe dans un espace de Hilbert H de grande dimension (>>n). Ceci est réalisé en utilisant un noyau qui va coder la similarité entre les sommets et dont la valeur est égale au produit scalaire dans H. L'utilisation de simples classifieurs linéaires dans H permet alors de révéler des regroupements de sommets difficiles à obtenir dans un espace de faible dimension (car non séparable linéairement). Cette méthodologie issue de l'étude des SVM (machines à vecteurs supports) a été généralisée à de nombreux algorithmes que nous utiliserons ici. - 3. La construction directe d'une mesure de similarité entre graphes. A la différence des points précédents, on n'exploite pas ici une représentation géométrique de chacun des deux graphes à comparer mais on construit directement une matrice de similarité entre les deux graphes. Etant donnés deux graphes G1 et G2 avec respectivement n et p sommets, l'entrée sij d'une matrice de similarité S à n lignes et p colonnes est un indice de similarité entre le ième sommet de G1 et le jème sommet de G2. Cette matrice est souvent obtenue comme la limite d'une suite de telles matrices. - Les graphes sur lesquels nous testerons ces approches seront issus d'une base de données d'environ 10000 contrats agraires issus de quatre fonds seigneuriaux distincts conservés aux archives départementales du Lot et du Tarn-et-Garonne et couvrant une période qui s'étire de 1250 à 1500. La problématique posés par les historiens concerne l'analyse de l'espace et de la sociabilité paysanne au Moyen-Age. - Nous proposons de décrire d'abord en détail cette problématique, puis cha