Le domaine de la modélisation du trafic routier vise à comprendre son évolution. Dans les dernières années, plusieurs modèles du trafic ont été proposés dans l’objectif de géolocaliser les embouteillages au sein du trafic, détecter des motifs dans le trafic routier, estimer l’état du trafic etc. La plupart des modèles proposés considèrent le trafic routier en termes de ses constituants ou comme une entité agrégée en fonction de l’échelle choisie et expliquent l’évolution du trafic quantitativement en tenant compte des relations entre les variables de trafic comme le flot, la densité et la vitesse. Ces modèles décrivent le trafic en utilisant des données très précises acquises par différents capteurs. La précision des données rend son calcul coûteux en termes de ressources requises. Une des solutions à ce problème est la représentation qualitative du trafic routier qui réduit le nombre de ressources de traitement nécessaires. Puisque le trafic routier est un phénomène spatio-temporel, les modèles proposés pour représenter ce type de phénomène pourraient être appliqués dans le cas du trafic routier. Les modèles spatio-temporels, proposés par la communauté de l’Analyse Spatio-Temporelle, ont comme objectif la représentation d’un phénomène tant du point de vue qualitatif que quantitatif. Certains de ces modèles proposent une discrétisation des phénomènes modélisés en considérant un phénomène comme constitué d’entités. Appliquée au trafic routier, cette notion permet d’identifier différentes entités, comme les véhicules, les piétons, les bâtiments etc., qui le constituent. Ces entités influent sur l’évolution du trafic. Les modèles spatio-temporels qualitatifs définissent l’effet des différentes entités les unes sur les autres en terme de relations spatiales. L’évolution spatio-temporelle du phénomène modélisé est représenté par la variation temporelle de ces relations. La prise en compte des entités du trafic et des relations spatiales formalise une structure qui peut être représentée en utilisant un graphe, où les nœuds modélisent des entités et les arcs des relations spatiales. Par conséquent, l’évolution du trafic, modélisée via ce graphe, devient l’évolution du graphe et peut être représenté en terme de la variation de la structure du graphe ainsi que celle des attributs de ses nœuds et de ses arcs. Dans cette thèse, nous proposons une modélisation du trafic routier de ce type basée sur la théorie des graphes. Une des applications à la modélisation du trafic routier est la détection des motifs pertinents au sein du trafic. Dans les modèles du trafic existants, les motifs détectés sont statistiques et sont représentés en utilisant des caractéristiques numériques. Le modèle que nous pro posons dans cette thèse met en avant la structure représentant le trafic routier et peut donc être utilisé pour définir des motifs structurels du trafic qui prennent en compte des différentes entités du trafic et leurs relations. Ces motifs structurels sont sous-jacents à une modélisation sous forme de graphe dynamique. Dans cette thèse, nous proposons un algorithme pour détecter ces motifs structurels du trafic dans le graphe spatio-temporel représentant le trafic routier. Ce problème est formalisé comme celui de l’isomorphisme de sous-graphe pour des graphes dynamiques. L’algorithme proposé est évalué en fonction desdifférents paramètres de graphes. / For past several decades, researchers have been interested in understanding traffic evolution, hence, have proposed various traffic models to identify bottleneck locations where traffic congestion occurs, to detect traffic patterns, to predict traffic states etc. Most of the existing models consider traffic as many-particle system, describe it using different scales of representation and explain its evolution quantitatively by deducing relations between traffic variables like flow, density and speed. Such models are mainly focused on computing precise information about traffic using acquired traffic data. However, computation of such precise information requires more processing resources. A way to remedy this problem is to consider traffic evolution in qualitative terms which reduces the required number of processing resources. Since traffic is spatio-temporal in nature, the models which deal with spatio-temporal phenomenon can be applied in case of traffic. Such models represent spatio-temporal phenomenon from qualitative as well as quantitative standpoints. Depending on the intended application, some models are able to differentiate between various entities taking part in the phenomenon, which proves useful in case of traffic since different objects like vehicles, buildings, pedestrians, bicycles etc., directly affecting traffic evolution, can be included in traffic models. Qualitative spatio-temporal models consider the effects of different entities on each other in terms of spatial relations between them and spatio-temporal evolution of the modeled phenomenon is described in terms of variation in such relations over time. Considering different traffic constituents and spatial relations between them leads to the formation of a structure which can be abstracted using graph, whose nodes represent individual constituents and edges represent the corresponding spatial relations. As a result, the evolution of traffic, represented using graph, is described in terms of evolution of the graph itself, i. e. change in graph structure and attributes of nodes and edges, with time. In this thesis, we propose such a graph model to represent traffic. As mentioned above, one of the applications of existing traffic models is in detecting traffic patterns. However, since such models consider traffic quantitatively, in terms of acquired traffic data, the patterns detected using such models are statistical (a term employed by Pattern Recognition researchers) in the sense that they are represented using numerical description. Since graph-based traffic model proposed in this thesis represents the structure of traffic, it can be employed to redefine the meaning of traffic patterns from statistical to structural (also a term from Pattern Recognition community). Structural traffic patterns include different traffic constituents and their inter-links and are represented using time-varying graphs. An algorithm to detect a given structural traffic pattern in the spatio-temporal graph representing traffic is proposed in this thesis. It formalizes this problem as subgraph isomorphism for time-varying graphs. In the end, the performance of the algorithm is tested using various graph parameters.

Cette thèse s'est déroulée dans le cadre du projet ANR FOSTER, "FOuille de données Spatio-Temporelles : application à la compréhension et à la surveillance de l'ERosion" (ANR-2010-COSI-012-02, 2011-2014). Dans ce contexte, nous nous sommes intéressés à la modélisation de données spatio-temporelles dans des graphes enrichis de sorte que des calculs de motifs sur de telles données permettent de formuler des hypothèses intéressantes sur les phénomènes à comprendre. Plus précisément, nous travaillons sur la fouille de motifs dans des graphes relationnels (chaque noeud est identifié de fa\c con unique), attribués (chaque noeud du graphe est décrit par des attributs qui sont ici numériques), et dynamiques (les valeurs des attributs et les relations entre les noeuds peuvent évoluer dans le temps). Nous proposons un nouveau domaine de motifs nommé motifs de co-évolution. Ce sont des triplets d'ensembles de noeuds, d'ensembles de pas de temps et d'ensembles d'attributs signés, c'est à dire des attributs associés à une tendance (croissance,décroissance). L'intérêt de ces motifs est de décrire un sous-ensemble des données qui possède un comportement spécifique et a priori intéressant pour conduire des analyses non triviales. Dans ce but, nous définissons deux types de contraintes, une contrainte sur la structure du graphe et une contrainte sur la co-évolution de la valeur des attributs portés par les noeuds. Pour confirmer la spécificité du motif par rapport au reste des données, nous définissons trois mesures de densité qui tendent à répondre à trois questions. À quel point le comportement des noeuds en dehors du motif est similaire à celui des noeuds du motif ? Quel est le comportement du motif dans le temps, est-ce qu'il apparaît soudainement ? Est-ce que les noeuds du motif ont un comportement similaire seulement sur les attributs du motif ou aussi en dehors ? Nous proposons l'utilisation d'une hiérarchie sur les attributs comme connaissance à priori de l'utilisateur afin d'obtenir des motifs plus généraux et adaptons l'ensemble des contraintes à l'utilisation de cette hiérarchie. Finalement, pour simplifier l'utilisation de l'algorithme par l'utilisateur en réduisant le nombre de seuils à fixer et pour extraire uniquement l'ensemble des motifs les plus intéressants, nous utilisons le concept de ``skyline'' réintroduit récemment dans le domaine de la fouille de données. Nous proposons ainsi trois algorithmes MINTAG, H-MINTAG et Sky-H-MINTAG qui sont complets pour extraire l'ensemble de tous les motifs qui respectent les différentes contraintes. L'étude des propriétés des contraintes (anti-monotonie, monotonie/anti-monotonie par parties) nous permet de les pousser efficacement dans les algorithmes proposés et d'obtenir ainsi des extractions sur des données réelles dans des temps raisonnables. / This thesis was conducted within the project ANR FOSTER, ``Spatio-Temporal Data Mining: application to the understanding and monitoring of erosion'' (ANR-2010-COSI-012-02, 2011-2014). In this context, we are interested in the modeling of spatio- temporal data in enriched graphs so that computation of patterns on such data can be used to formulate interesting hypotheses about phenomena to understand. Specifically, we are working on pattern mining in relational graphs (each vertex is uniquely identified), attributed (each vertex of the graph is described by numerical attributes) and dynamic (attribute values and relations between vertices may change over time). We propose a new pattern domain that has been called co-evolution patterns. These are trisets of vertices, times and signed attributes, i.e., attributes associated with a trend (increasing or decreasing). The interest of these patterns is to describe a subset of the data that has a specific behaviour and a priori interesting to conduct non-trivial analysis. For this purpose, we define two types of constraints, a constraint on the structure of the graph and a constraint on the co-evolution of the value worn by vertices attributes. To confirm the specificity of the pattern with regard to the rest of the data, we define three measures of density that tend to answer to three questions. How similar is the behaviour of the vertices outside the co-evolution pattern to the ones inside it? What is the behaviour of the pattern over time, does it appear suddenly? Does the vertices of the pattern behave similarly only on the attributes of the pattern or even outside? We propose the use of a hierarchy of attributes as an a priori knowledge of the user to obtain more general patterns and we adapt the set of constraints to the use of this hierarchy. Finally, to simplify the use of the algorithm by the user by reducing the number of thresholds to be set and to extract only all the most interesting patterns, we use the concept of ``skyline'' reintroduced recently in the domain of data mining. We propose three constraint-based algorithms, called MINTAG, H-MINTAG and Sky-H-MINTAG, that are complete to extract the set of all patterns that meet the different constraints. These algorithms are based on constraints, i.e., they use the anti-monotonicity and piecewise monotonicity/anti-monotonicity properties to prune the search space and make the computation feasible in practical contexts. To validate our method, we experiment on several sets of data (graphs) created from real-world data.

Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamique. / Dynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs.