Ce projet de thèse CIFRE est centré sur le développement de méthodes, d’algorithmes et d’heuristiques pour la génération, la gestion, l’exploration et l’analyse de grands graphes de données sur des entités nommées obtenus à partir de données textuelles (hypothèses). Ce corpus d’hypothèses est alimenté régulièrement par de nouvelles hypothèses. Les hypothèses se recoupent entre elles et dénotent plusieurs types d’interactions entre des entités nommées. Par conséquent, les grands graphes qui seront étudiés sont dynamiques et atteindront à moyens termes des milliards de nœuds.
Notre objectif, dans un premier temps, est de construire une grammaire de graphes capable de générer des graphes de données à partir de ce corpus d’hypothèses. Ces graphes peuvent être des (multi-)graphes, orientés ou pondérés aux niveaux nœuds et/ou arcs. Ils peuvent contenir un nombre extrêmement important de nœuds (de l’ordre de milliards de nœuds). De plus, ces graphes sont dynamiques et évoluent avec l’arrivée de nouvelles hypothèses dans le corpus.
Dans un deuxième temps, nous serons amenés à proposer des algorithmes efficaces de gestion de ces graphes, avec comme objectif leur passage à l’échelle. En particulier, nous nous intéresserons à deux problématiques importantes : (1) le partitionnement de graphes et (2) la distribution de graphes sur des architectures distribuées. Le problème de partitionnement de graphes est NP-difficile même pour des classes particulières de graphes. De plus, les méthodes de partitionnement des plateformes de grands graphes existantes sont basiques et indépendantes des applications étudiées. Nous serons amenés dans cette thèse à développer des heuristiques efficaces capables de partitionner nos graphes avec des contraintes spécifiques liées aux types de requêtes que nous souhaitons traiter et aux contraintes liées à la plateforme comme l’équilibrage de charge, la synchronisation, la tolérance aux pannes, etc. Les partitions obtenues seront par la suite distribuées sur une architecture de type Hadoop/MapReduce. Une politique de distribution est nécessaire afin que l’exploration du graphe et son analyse se fassent efficacement et dans des temps raisonnables.