Supervision : Emmanuel CHAILLOUX

Co-supervision : BUI-XUAN Binh-Minh, MIACHON Cédric

Enumération de motifs temporels

Un graphe temporel G peut être représenté comme une suite de graphes statiques G(t) indexés par un ensemble d'instants temporels. Ce formalisme permet de modéliser le comportement et les interactions d'agents divers ainsi que la temporalité de ces interactions. La recherche de motifs temporels dans ce formalisme correspond alors à l'identification des similitudes de comportement ou à la recherche de comportements spécifiques dans la temporalité de ces interactions.
Ces motifs temporels peuvent revêtir divers aspects et leur identification et leur énumération peut correspondre à différents problèmes.
Dans cette thèse, je considère deux de ces problèmes, l'énumération de Delta-jumeaux et l'énumération de sous-graphes temporels isomorphes à un motif, avec pour objectif de caractériser des populations par leurs interactions dans le cadre de cycles d'achat.
Les graphes sur lesquels je réalise mes expériences, tirés de données d'exploitation réelle, présentent une taille d'historique, c'est-à-dire un nombre d'instants temporels entre le premier instant t0 pour lequel G(t0) n'est pas vide et le dernier instant tf pour lequel G(tf) n'est pas vide, de l'ordre de plusieurs millions d'instants temporels. Du fait de cette taille importante, je me concentre particulièrement sur l'influence de la taille de l'historique du graphe temporel sur le temps de calcul des algorithmes proposés.
Le premier problème traité par cette thèse est le problème d'énumération des Delta-modules d'un graphe. Étant donné un entier Delta, un Delta-module est un ensemble de sommets A ayant le même voisinage en dehors de A pour Delta instants consécutifs. Un tel sous-ensemble peut par exemple s'avérer utile pour identifier des populations ayant des comportements similaires sur des périodes données, mais pouvant se comporter différemment en dehors de ces périodes. En utilisant une structure de données basée sur les arbres rouge-noir, je donne une solution au problème d'énumération de Delta-modules en temps quadratique de tau et au cas spécifique d’énumération des Delta-jumeaux en temps logarithmique de tau.
Le deuxième problème consiste en l'énumération des sous-graphes temporels de G isomorphes à un deuxième graphe temporel appelé "motif". Étant donné un deuxième graphe temporel P, l'isomorphisme de sous-graphes temporels est une paire constituée d'un instant temporel de G et d'une bijection des sommets de P vers un sous-ensemble de sommets de G. Cette bijection doit être telle qu'à partir de l'instant temporel en question, les images des sommets de P par la bijection présentent le même comportement interactif entre eux que les sommets dont ils sont l'image. Une telle bijection permet par exemple d'identifier des motifs comportementaux permettant d'appréhender des relations de contingence ou de causalité au sein de cycles d'achat. En utilisant le lien entre isomorphisme de sous-graphes statiques et la recherche de cliques de taille n, je donne une solution au problème d'énumération des sous-graphes temporels isomorphes, avec une complexité temporelle linéaire en la taille de l'historique. ??????L'étude expérimentale des solutions des problèmes d'énumération de Delta-modules et d'énumération de sous-graphes temporels isomorphes confirme une limite, anticipée par l'étude théorique, aux tailles des graphes temporels traitables par ces algorithmes. Selon l'analyse numérique, et sachant que sur les jeux de données que je traite dans cette thèse, une seconde de temps réel sépare deux instants temporels successifs du graphe, mes expérimentations sur des graphes obtenus à partir de données du monde réel passent à l'échelle dans les cas spécifiques de l'énumération des Delta-jumeaux jusqu'à une taille d'historique de 10^8 instants temporels, soit 3 ans et 2 mois, et dans le cas spécifique des sous-graphes temporels isomorphes jusqu'à une taille d'historique de 10^6 instants temporels, qui équivaut à 11 jours et demi d'historique.

2020-2023 Publications

• 2023
  • H. Hourcade : “Enumération de motifs temporels”, thesis, phd defence 05/16/2023, supervision Chailloux, Emmanuel, co-supervision : Bui-xuan, Binh-Minh, Miachon, Cédric (2023)
• 2022
  • B.‑M. Bui‑Xuan, H. Hourcade, C. Miachon : “Computing Small Temporal Modules in Time Logarithmic in History Length”, Social Network Analysis and Mining, (Springer) (2022)
• 2020
  • B.‑M. Bui‑Xuan, H. Hourcade, C. Miachon : “Computing Temporal Twins in Time Logarithmic in History Length”, 9^th International Conference on Complex Networks and their Applications, Madrid, Spain (2020)