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.

Data generated by the evolution of entities and their interconnectivity in real-world sce-narios has become crucial for answering questions related to various phenomena and thenmaking well-informed decisions. As an example, contact tracing data records interactionsbetween infected individuals and their contacts. The ‘what’, ‘who’, and ‘where’ ques-tions about the disease contagion described in those interconnected data can be answered without considering their evolution. Delving into ‘when’ and ‘how’ questions requires considering evolution. To do so, Temporal Graph (TG) has emerged over the past decade as a new solution to address the evolution of interconnected data. Beyond the concept of TG, this thesis aims at exploring how to design, implement, query and discover knowledge.As a relatively new concept, TG has no standard definition. The concept is used indiverse fields (from graph theory to databases) and generally designates a graph modelintegrating time dimension. Existing TG models partially capture the evolution aspectsof real-world scenarios. Moreover, they are not directly implementable with classic graphdata stores (e.g., Neo4j). Our first contribution is therefore a complete solution composedby (i) an enriched conceptual modelling of TG which captures all evolution aspects ofreal-world scenarios, (ii) mapping rules from our TG model to classic graph models, and(iii) experiments validating the efficiency and scalability of our solution.The thesis then explores querying solutions. Existing querying solutions for TG allowcrossing the interconnectivity and temporal dimensions of TG. They enable to retrieveinformation in TG answering ‘what’, ‘who’, ‘where and ‘when’ questions. However, theyare limited in terms of analysis capabilities or difficult to implement. Our second contri-bution addresses this issue by proposing a complete solution including (i) a conceptualquery algebra based on our TG model’s concepts, (ii) mapping rules from our query alge-bra to classic textual graph query languages (e.g., Cypher of Neo4j), and (iii) experimentsvalidating the feasibility of our solution.Finally, the thesis investigates the discovery of evolution mechanisms in TG to helpanswer the ‘how’ questions about phenomena in TG. In TG field, Pattern Mining is apowerful technique to extract patterns using algorithms. Patterns are combinations ofinformation pieces representing evolution mechanisms in TG. Our third contribution istherefore composed of (i) the definition of a novel pattern type which captures all evolution aspects in our TG model to describe richer evolution mechanisms than existing patterns, (ii) a novel algorithm to extract this pattern, and (iii) experiments confirming the interest of our pattern and the algorithm’s efficiency.