Thèse de Abd Errahmane Kiouche


Sujet :
Appariement de graphes et données massives

Résumé :

La comparaison de graphes, plus connue sous le nom de matching (ou appariement) de graphes est un domaine de recherche très actif traité par plusieurs communautés : recherche d’information, reconnaissance de formes, bases de données, etc. Les solutions existantes peuvent être classifiées en exactes ou approchées selon le résultat attendu de la comparaison. Les méthodes exactes permettent de trouver les graphes résultats qui sont exactement similaires au graphe requête.  Les méthodes approchées permettent de calculer une sorte de distance qui reflète de manière approchée le degré de ressemblance entre les deux graphes comparés. Cela permet d’avoir les résultats les plus proches du graphe requête lorsqu’on a plusieurs graphes à comparer avec. C’est ce qu’on appelle le top k (comme avec un moteur de recherche).

Les approches algorithmiques pour comparer deux graphes, en particulier dans le cas exact, ont un comportement exponentiel et deviennent difficiles à mettre en place dès lors que la taille des graphes devient vraiment importante. Une problématique similaire se pose même dans le cas des méthodes approchées. Comme la taille des graphes de données ou des bases de données graphes ne fait qu’augmenter, il devient critique de proposer des outils de comparaison faciles à mettre en place et qui passent l’échelle. C’est l’objectif de cette thèse.

Diverses approches pourront être envisagées. Une des approches les plus efficaces est de décomposer les deux graphes à comparer en petits morceaux, de comparer les morceaux et ensuite en déduire un résultat pour la comparaison des deux graphes initiaux soit par jointure des résultats intermédiaires soit par un calcul de distance.  La comparaison de graphes à travers la décomposition peut être utilisée dans le cas exact ainsi que dans le cas inexact d’où sa puissance. Dans ce cas, le verrou scientifique consiste à trouver la meilleure décomposition qui permet de diminuer le nombre de jointures nécessaires pour l’obtention du résultat final, en particulier dans le cas exact. Une autre approche plus récente s’intéresse à la manière avec laquelle sont représentés les graphes et les nœuds. Il s’avère en effet, qu’avec une représentation adaptée (plus compacte, plus simple, etc.), on peut simplifier de loin la comparaison des graphes. Il existe aussi des solutions qui utilisent des plateformes spécialisées dans le traitement du big data comme MapReduce et Pregel.

Le but de cette thèse est donc d’étudier l’algorithmique autour de la comparaison de graphes et de proposer des solutions de comparaison et d’appariement qui peuvent être utiliser efficacement dans le cas de grands graphes ou d’un nombre important de graphes. Nous allons principalement considérer les modèles de données adaptés aux grands graphes tels que les flux de graphes et plusieurs domaines d'application.


Encadrant : Hamida Seba