Andriamampianina, Landy (2023) Graphes Temporels : De la modélisation à l'analyse. École doctorale Mathématiques, Informatique et Télécommunications (Toulouse).

Preview

Text Download (7MB) | Preview

Abstract

Les données générées par l'évolution des entités et leur interconnectivité dans des scénarios du monde réel sont devenues cruciales pour répondre à des questions liées à divers phénomènes et prendre ensuite des décisions éclairées. À titre d'exemple, les données de traçage des contacts enregistrent les interactions entre les individus infectés et leurs contacts. Les questions "quoi", "qui" et "où" concernant la contagion de la maladie décrite dans ces données interconnectées peuvent être répondues sans tenir compte de leur évolution. Les questions "quand" et "comment" nécessite de prendre en compte l'évolution. Pour ce faire, le Graphe Temporel (GT) est apparu au cours de la dernière décennie comme une nouvelle solution pour aborder l'évolution des données interconnectées. Au-delà du concept de GT, cette thèse vise à explorer comment concevoir, implémenter, interroger et découvrir des connaissances.

En tant que concept relativement nouveau, le TG n'a pas de définition standard. Le concept est utilisé dans divers domaines (de la théorie des graphes aux bases de données) et désigne généralement un modèle de graphe intégrant la dimension temporelle. Les modèles de TG existants capturent partiellement les aspects de l'évolution des scénarios du monde réel. De plus, ils ne sont pas directement applicables avec les systèmes de stockage de données graphes classiques (par exemple, Neo4j). Notre première contribution est donc une solution complète composée (i) d'une modélisation conceptuelle enrichie du TG qui capture tous les aspects de l'évolution des scénarios du monde réel, (ii) des règles de mise en correspondance de notre modèle de TG avec les modèles de graphes classiques, et (iii) des expérimentations validant l'efficacité et la scalabilité de notre solution.

La thèse explore ensuite des solutions d'interrogation. Les solutions d'interrogation existantes pour le GT permettent de croiser les dimensions d'interconnectivité et temporelle du GT. Elles permettent de récupérer des informations dans le GT répondant aux questions "quoi", "qui", "où" et "quand". Cependant, elles sont limitées en termes de capacités d'analyse ou difficiles à mettre en œuvre. Notre deuxième contribution aborde cette question en proposant une solution complète comprenant (i) une algèbre de requête conceptuelle basée sur les concepts de notre modèle de TG, (ii) des règles de mise en correspondance de notre algèbre de requête avec les langages de requête graphique textuels classiques (par exemple, Cypher de Neo4j), et (iii) des expérimentations validant la faisabilité de notre solution.

Enfin, la thèse explore la découverte des mécanismes d'évolution dans le TG pour aider à répondre aux questions "comment" concernant les phénomènes dans le TG. Dans le domaine du TG, l'extraction de motifs est une technique puissante pour extraire des motifs à l'aide d'algorithmes. Les motifs sont des combinaisons de morceaux d'informations représentant les mécanismes d'évolution dans le GT. Notre troisième contribution est donc composée de (i) la définition d'un nouveau type de motif qui capture tous les aspects de l'évolution dans notre modèle de TG pour décrire des mécanismes d'évolution plus riches que les motifs existants, (ii) un nouvel algorithme pour extraire ce motif, et (iii) des expérimentations confirmant l'intérêt de notre motif et l'efficacité de l'algorithme.