Énumération de motifs temporels

Dans le cadre de l'étude des interactions de divers acteurs au sein d'un système, la recherche de schémas comportementaux trouve nombre d'applications. Les graphes temporels qui m'intéressent dans le cadre de cette thèse présentent des tailles d'historiques tau, à savoir le nombre d'instants temporels entre le premier instant t0 et le dernier instant tf pour lesquels G n'est pas vide, de l'ordre de plusieurs millions. Je cherche donc à minimiser l'impact de tau sur les complexités spatiales et temporelles de mes algorithmes. Étant donné Delta un entier naturel, l'énumération de Delta-modules est l'énumération de tous les sous-ensemble de sommets A d'un graphe temporel L(V,E,T) tels que pour tout instant temporel t dans un intervalle de Delta instants consécutifs ou plus, les voisinages instantanés de chaque sommet de A en dehors de A soient égaux. Je présente un algorithme utilisant l'affinage de partition et des structures de données d'arbre rouge-noir pour énumérer les Delta-modules en temps quadratique de tau. L'énumération des Delta-jumeaux, pour lesquels |A|=2 est réalisée en temps logarithmique de tau avec une utilisation mémoire indépendante de tau. Étant donné H(V',E',T') un graphe temporel appelé motif, l'énumération de sous-graphes de L(V,E,T) isomorphes à H est l'énumération de toutes les paires constituées d'un instant temporel t0 de T et d'une bijection f de V' vers un sous-ensemble A de V telles qu'à chaque instant temporel entre t0 et t0+tau', les sommets de H aient exactement le même comportement entre eux à l'instant t que leurs images par f dans L à l'instant t0+t. J'établis un algorithme énumérant les sous-graphes temporels isomorphes en temps linéaire de tau. Après avoir présenté et démontré la correction et les complexités de ces divers algorithmes, je conduis une étude expérimentale afin de confirmer par la pratique le comportement de mes algorithmes.