Spatio-temporal pattern detection in spatio-temporal graphs

Use case of invasive team sports and urban road traffic

Détection de modèles spatio-temporels dans les graphes spatio-temporels. Cas d’utilisation des sports d’équipe invasifs et du trafic routier urbain

¹ IRIT, University of Toulouse, UT3, Toulouse
² Normandie University, INSA Rouen, LITIS, 76000, Rouen

Abstract

Spatio-temporal (ST) graphs have been used in many application domains to model evolving ST phenomenon. Such models represent the underlying structure of the phenomenon in terms of its entities and different types of spatial interactions between them. The reason behind using graph-based models to represent ST phenomenon is due to the existing well-established graph analysis tools and algorithms which can be directly applied to analyze the phenomenon under consideration. In this paper, considering the use case of two distinct, highly dynamic phenomena - invasive team sports, with a focus on handball and urban road traffic, we propose a spatio-temporal graph model applicable to both these phenomena. Different types of entities and spatial relations which make up these phenomena are highlighted to formalize the graph. Furthermore, the idea of graph-based pattern detection in both these phenomena is explored. Different types of ST patterns for both ST phenomena are discussed and the problem of pattern detection is formalized as the problem of subgraph isomorphism for dynamic graphs. Finally, the results of our algorithm to detect random ST patterns in random ST graphs are presented. The ideas discussed in this paper are applicable to other ST phenomena as well.

Résumé

Les graphes spatio-temporels sont utilisés dans de nombreux domaines d’application pour modéliser les phénomènes spatio-temporels. Ces modèles représentent la structure sousjacente du phénomène en termes d’entités et de différents types d’interactions spatiales entre elles. La motivation d’utiliser des modèles à base de graphes pour représenter le phénomène ST est due à l’existence d’outils et d’algorithmes d’analyse de graphes bien établis qui peuvent être directement appliqués pour analyser le phénomène considéré. Dans cet article, en considérant le cas d’usage de deux phénomènes distincts et très dynamiques - les sports collectifs, avec un regard particulier sur le handball et le trafic routier urbain, nous proposons un modèle de graphe spatio-temporel applicable à ces deux phénomènes. Les différents types d’entités et les relations spatiales qui composent ces phénomènes sont soulignés pour formaliser ce graphe. En outre, nous explorons l’ideé de la détection de motifs basés sur les graphes dans le handball et le trafic routier urbain. Différents types de motifs spatio-temporels pour les deux phénomènes spatio-temporels sont discutés et le problème de la détection des motifs est formalisé comme le problème de l’isomorphisme des sous-graphes pour les graphes dynamiques. Enfin, les résultats de notre algorithme de détection de motifs spatio-temporels aléatoires dans les graphes aléatoires sont présentés. Les idées discutées dans cet article sont également applicables à d’autres phénomènes spatio-temporels.