Search

National audience; This work is carried out in the framework of the IRN Zoomathia which aims to study the transmission of zoo- logical knowledge from Antiquity to the Middle Ages. In this context, a first work of manual annotation of Pline’s Naturalis Historia (books 8-11) on ancient zoology using concepts gathered in the thesaurus TheZoo was done by classicists. However, these annotations have been stored as comments in Word documents, which complicates the exploitation of this knowledge by epistemology, history and philiology researchers in their analysis of these ancient texts. In this article, we present our approach to transform manual annotations into an RDF knowledge graph allowing the integration and the interrogation of relevant knowledge in order to support researchers in their analysis of these texts and knowledge transmission through them. In order to validate the relevance of the model as well as the knowledge graph, we elicited from a domain expert a set of competency questions that we translated in SPARQL to answer them by querying the knowledge graph.; Ce travail est réalisé dans le cadre de l'IRN Zoomathia qui vise l'étude de la transmission des savoirs zoologiques de l'Antiquité au Moyen Âge. Dans ce contexte, un premier travail d'annotation manuelle de l'"Histoire Naturelle" de Pline l'Ancien sur la zoologie antique (livres 8-11) en utilisant des concepts rassemblés dans le thésaurus The-Zoo a été réalisé par des spécialistes de l'Antiquité. Cependant, ces annotations ont été réalisées avec des commentaires Word, ce qui rend complexe l'exploitation de ces connaissances par les chercheurs épistémologues, historiens et philologues dans leur travail d'analyse de ces textes anciens. Dans cet article, nous présentons notre approche de transformation de ces annotations manuelles en graphe de connaissance RDF permettant l'intégration et l'interrogation des connaissances extraites dans le but d'aider les chercheurs dans leur travail d'analyse de ces textes et de la transmission des connaissances à travers eux. Afin de valider la pertinence du modèle et le graphe de connaissance, nous avons recueilli auprès d'un expert du domaine un ensemble de questions de compétences que nous avons traduites en SPARQL pour y répondre en interrogeant le graphe de connaissance produit.

International audience

International audience

International audience; With the significant increase of interactions between individuals through numeric means, the clustering of vertex in graphs has become a fundamental approach for analysing large and complex networks. We propose here the deep latent position model (DeepLPM), an end-to-end clustering approach which combines the widely used latent position model (LPM) for network analysis with a graph convolutional network (GCN) encoding strategy. Thus, DeepLPM can automatically assign each node to its group without using any additional algorithms and better preserves the network topology. Numerical experiments on simulated data and an application on the Cora citation network are conducted to demonstrate its effectiveness and interest in performing unsupervised clustering tasks.

National audience; Comparing structured objects such as graphs is a fundamental operation involved in many learning tasks. To this end, the Gromov-Wasserstein (GW) distance, based on Optimal Transport (OT), has been successful in providing meaningful comparison between such entities.GW operates on graphs, seen as probability measures over spaces depicted by their nodes connectivity relations. At the core of OT is the idea ofmass conservation, which imposes a coupling between all the nodes from the two considered graphs. We argue in this paper that this property can be detrimental for tasks such as graph dictionary learning (DL), and we relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence.The latter leads to immediate computational benefits and naturally induces a new graph DL method, shown to be relevant for unsupervisedrepresentation learning and classification of graphs; -La comparaison d'objets structurés tels que les graphes est une opération fondamentale pour de nombreuses tâches d'apprentissage. À cette fin, la distance de Gromov-Wasserstein (GW) , basée sur le Transport Optimal (TO), s'est avérée efficace pour comparer de telles entités. GW opère sur les graphes, vus comme des mesures de probabilité sur des espaces décrits par les relations de connectivité de leurs noeuds. Au coeur du TO réside l'idée de conservation de masse, qui impose un couplage entre tous les noeuds des deux graphes considérés. Nous soutenons dans ce papier que cette propriété peut être préjudiciable pour des tâches telles que l'apprentissage de dictionnaire (AD), et nous la relaxons donc en proposant une nouvelle divergence issue de GW. Cette dernière amène des avantages computationnels immédiats et induit naturellement une nouvelle méthode d'AD, pertinente pour l'apprentissage non supervisé de représentations et la classification de graphes.

With the significant increase of interactions between individuals through numeric means, clustering of vertices in graphs has become a fundamental approach for analyzing large and complex networks. In this work, we propose the deep latent position model (DeepLPM), an end-to-end generative clustering approach which combines the widely used latent position model (LPM) for network analysis with a graph convolutional network (GCN) encoding strategy. Moreover, an original estimation algorithm is introduced to integrate the explicit optimization of the posterior clustering probabilities via variational inference and the implicit optimization using stochastic gradient descent for graph reconstruction. Numerical experiments on simulated scenarios highlight the ability of DeepLPM to self-penalize the evidence lower bound for selecting the intrinsic dimension of the latent space and the number of clusters, demonstrating its clustering capabilities compared to state-of-the-art methods. Finally, DeepLPM is further applied to an ecclesiastical network in Merovingian Gaul and to a citation network Cora to illustrate the practical interest in exploring large and complex real-world networks.

We create a framework to analyse the timing and frequency of instantaneous interactions between pairs of entities. This type of interaction data is especially common nowadays, and easily available. Examples of instantaneous interactions include email networks, phone call networks and some common types of technological and transportation networks. Our framework relies on a novel extension of the latent position network model: we assume that the entities are embedded in a latent Euclidean space, and that they move along individual trajectories which are continuous over time. These trajectories are used to characterize the timing and frequency of the pairwise interactions. We discuss an inferential framework where we estimate the individual trajectories from the observed interaction data, and propose applications on artificial and real data., 33 pages

Comparing structured objects such as graphs is a fundamental operation involved in many learning tasks. To this end, the Gromov-Wasserstein (GW) distance, based on Optimal Transport (OT), has proven to be successful in handling the specific nature of the associated objects. More specifically, through the nodes connectivity relations, GW operates on graphs, seen as probability measures over specific spaces. At the core of OT is the idea of conservation of mass, which imposes a coupling between all the nodes from the two considered graphs. We argue in this paper that this property can be detrimental for tasks such as graph dictionary or partition learning, and we relax it by proposing a new semi-relaxed Gromov-Wasserstein divergence. Aside from immediate computational benefits, we discuss its properties, and show that it can lead to an efficient graph dictionary learning algorithm. We empirically demonstrate its relevance for complex tasks on graphs such as partitioning, clustering and completion., Published as a conference paper at ICLR 2022

We consider mixtures of longitudinal trajectories, where one trajectory contains measurements over time of the variable of interest for one individual and each individual belongs to one cluster. The number of clusters as well as individual cluster memberships are unknown and must be inferred. We propose an original Bayesian clustering framework that allows us to obtain an exact finite-sample model selection criterion. Our approach is more flexible and parsimonious than asymptotic alternatives such as Bayesian Information Criterion (BIC) or Integrated Classification Likelihood (ICL) criterion in the choice of the number of clusters. Moreover, our approach has other desirable qualities: i) it keeps the computational effort of the clustering algorithm under control and ii) it generalizes to several families of regression mixture models, from linear to purely non-parametric.

International audience; We consider here the problem of co-clustering count matrices with a high level of missing values that may evolve along the time. We introduce a generative model, named dynamic latent block model (dLBM), to handle this situation and which extends the classical binary latent block model (LBM) to the dynamic case. The modeling of the dynamic time framework in a continuous time relies on a non-homogeneous Poisson process, with a latent partition of time intervals. The continuous time is handled by a time partition over the whole considered time period, where the interactions are aggregated on the time intervals of such partition obtaining a sequence of static matrices that allows us to identify meaningful time clusters. We proposed to use the SEM-Gibbs algorithm for model inference and the ICL criterion for model selection. Finally, an application with real-world data is proposed.

International audience; We introduce a deep latent recommender system (deepLTRS) for imputing missing ratings based on the observed ratings and product reviews. Our approach extends a standard variational autoen-coder architecture associated with deep latent variable models in order to account for both the ordinal entries and the text entered by users to score and review products. DeepLTRS assumes a latent representation of both users and products, allowing a natural visualisation of the positioning of users in relation to products. Numerical experiments on simulated and real-world data sets demonstrate that DeepLTRS outperforms the state-of-the-art, in particular in contexts of extreme data sparsity.

International audience; Nous considérons le problème du co-clustering des matrices binaires qui peuvent évoluer dans le temps et nous introduisons un modèle génératif pour le gérer. Le modèle proposé, appelé dynamic latent block model, étend le modèle des blocs latents binaire classique au cas dynamique. La modélisation de la dynamique en temps continu repose sur un processus de Poisson non homogène, avec une partition latente des intervalles de temps. Nous proposons d'utiliser l'algorithme SEM-Gibbs pour l'inférence du modèle. Abstract. We consider the problem of co-clustering binary matrices that may evolved along the time and we introduce a generative model to handle it. The proposed model, named dynamic latent block model, extend the classical binary latent block model to the dynamic case. The modeling of the dynamic in a continuous time relies on a non-homogeneous Poisson process, with a latent partition of time intervals. We proposed to use the SEM-Gibbs algorithm for model inference.

Graphs are mathematical structures very suitable to model interactions between objects or actors of interest.Several real networks such as communication networks, financial transaction networks, mobile telephone networks and social networks (Facebook, Linkedin, etc.) can be modeled via graphs. When observing a network, the time variable comes into play intwo different ways: we can study the time dates at which the interactions occur and/or the interaction time spans. This thesis only focuses on the first time dimension and each interaction is assumed to be instantaneous, for simplicity. Hence, the network evolution is given by the interaction time dates only. In this framework, graphs can be used in two different ways to model networks:1) Discrete time. A network is observed at several times and a graph is associated with each observation time. Two nodes of a graph are connected if one or more interactions occurred between them in the corresponding time frame. Thus, interactions are aggregated between two consecutive observation times and the exact interaction dates are lost. In this context, a dynamic network is represented by a sequence of graphs.2) Continuous Time. Several edges are allowed to connect the nodes of a graph at different times. One edge is uniquely associated with a pair of nodes and a time point. No aggregation is required and interaction times are never lost. Therefore, a dynamic network is represented by a single multiple graph whose edges are labeled by the interaction times.In this thesis both these perspectives are adopted, alternatively. We consider new unsupervised methods to cluster the nodes of a graph into groups of homogeneous connection profiles. In this manuscript, the node groups are assumed to be time invariant to avoid possible identifiability issues. Moreover, the approaches that we propose aim to detect structural changes in the way the node clusters interact with each other. The building block of this thesis is the stochastic block model (SBM), a probabilistic approach initially used in social sciences. The standard SBM assumes that the nodes of a graph belong to hidden (disjoint) clusters and that the probability of observing an edge between two nodes only depends on their clusters. Since no further assumption is made on the connection probabilities, SBM is a very flexible model able to detect different network topologies (hubs, stars, communities, etc.).By adapting the block modeling perspective of SBM to dynamic graphs, the main contributions of this thesis are the following:1. We introduce a new extension of SBM for dynamic graphs. The proposed approach, called dSBM, adopts non homogeneous Poisson processes to model the interaction times between pairs of nodes in dynamic graphs, either in discrete or continuous time. The intensity functions of the processes only depend on the node clusters, in a block modeling perspective. Moreover, all the intensity functions share some regularity properties on hidden time intervals that need to be estimated.2. A recent estimation algorithm for SBM, based on the greedy maximization of an exact criterion (exact ICL) is adopted for inference and model selection in dSBM. To the best of our knowledge, this is the first time this algorithm is adopted for inference in dynamic stochastic block models.3. An exact algorithm for change point detection in time series, the "pruned exact linear time" (PELT) method is extended to deal with dynamic graph data modeled via dSBM. The approach we propose can be used for change point analysis in graph data. 4. A further extension of dSBM is developed to analyze dynamic networks with textual edges (like social networks, for instance). In this context, the graph edges are associated with documents exchanged between the corresponding nodes. The textual content of the documents can provide additional information about the dynamic graph topological structure. The new model we propose is called "dynamic stochastic topic block model" (dSTBM).This manuscript is organized as follows. In the first chapter, we pass through the main notions of graph theory and review some stylized facts about real networks. Two formal definitions of dynamic graph are provided. Then, the main existing generative models for static and dynamic random graphs are presented along with their associated inference procedures. Finally, some statistical tools not necessarily related with network analysis are described in detail since they are used in later chapters.In the second chapter, two versions of dSBM are introduced, both dealing with discrete time dynamic graphs. The corresponding inference procedure aims to maximize the complete data integrated log-likelihood, thus allowing us to learn the model parameters and select the number of clusters at the same time. In the third chapter, we model continuous time dynamic graphs via dSBM and focus on clustering and change point analysis in graph data. A standard variational approach is adopted for the inference and one step of the estimation algorithm relies on the PELT method.Finally, the fourth chapter introduces the dSTBM for discrete time dynamic graph with textual edges. The inference procedure is detailed and a model selection criterion is formally obtained.The last part of each chapter is devoted to experiments on both simulated and real data. These experiments allow us to highlight the features of the proposed approaches and to compare them with alternative methods., Les graphes sont des structures mathématiques très adaptées pour modéliser les interactions parmi des objet/individus à étudier. De nombreux types de réseaux réels peuvent être modélisés à travers des graphes, tels que les réseaux de transport, les réseaux de transactions financières ou les réseaux sociaux comme Facebook ou Linkedin. Quand on observe un réseau d'interactions, le tempsentre en jeu de deux manières différentes: on peut étudier les instants auxquels les interactions ont lieu et les durées de ces interactions. Les travaux de cette thèse se limitent à la première dimension temporelle. Chaque interaction est donc considérée comme instantanée pour des raisons de simplicité. L'évolution du réseau repose ainsi sur les temps des interactions uniquement. Dans ce contexte, les graphes peuvent être utilisés de deux manières différentes pour modéliser les réseaux:1) Temps discret. Un réseau est observé à des instants différents et un graphe est associé à chacun de ces instants. Deux nœuds d'un graphe sont connectés si une ou plusieurs interactions entre eux sont observées dans le réseau à l'instant correspondant. Les interactions sont donc agrégées entre un instant d'observation et le suivant et les dates exactes des interactions sont perdues. Un réseau dynamique est enfin représenté par une séquence de graphes. 2)Temps continu. Plusieurs arcs connectent les nœuds d'un graphe. Chaque arc est donc uniquement associé à une paire de nœuds et à un instant temporel. Il n'y a pas d'agrégation temporelle dans ce cas et les instants exacts des interactions ne sont pas perdus. Le réseau dynamique est donc représenté par un seul graphe multiple dont les arcs sont étiquetés par les temps d'interaction. Dans cette thèse ces deux visions sont adoptées alternativement. Nous proposons de nouvelles méthodes d'apprentissage non supervisé qui visent à partitionner les sommets d'un graphe dynamique en classes homogènes au sens où les sommets d'une même classe ont des profils d'interaction similaires. Pour éviter des problèmes d'identifiabilité les groupes de nœuds ne changent pas dans le temps. Par ailleurs, les approches proposées visent à détecter des changements structurels dans la façon dont les groupes de nœuds interagissent entre eux. Le point de départ de cette thèse est le stochastic block model (SBM), une approche probabiliste initialement utilisée en sciences sociales. Dans la version standard du modèle, les nœuds d'un graphe sont répartis dans des classes et la probabilité d'apparition d'un arc entre deux nœuds dépend uniquement des classes auxquelles ils appartiennent. Comme aucune hypothèse n'étant faite sur les probabilités d'interaction, SBM est un modèle très flexible qui permet de capturer des structures topologiques différentes et variées (hubs, stars, communautés, etc.). Tout en gardant une approche de modélisation par blocs (comme dans SBM) dans le contexte des graphes dynamiques,les principales contributions de cette thèse sont les suivantes:1) Nous introduisons une nouvelle extension dynamique du SBM, appelée dSBM, qui utilise des processus de Poisson non homogènes pour modéliser les interactions parmi les paires de nœuds d'un graphe dynamique, en temps discret et continu. Les fonctions d'intensité des processus ne dépendent que des classes des nœuds comme dans SBM. De plus, ces fonctions d'intensité ont des propriétés de régularité sur des intervalles temporels qui sont à estimer, et à l'intérieur desquels les processus de Poisson redeviennent homogènes.2) Un récent algorithme d'estimation pour SBM, qui repose sur la maximisation d'un critère exact (ICL exacte) est ici adopté pour estimer les paramètres de dSBM et sélectionner simultanément le modèle optimal. notre connaissance, c'est la première fois que cet algorithme est utilisé dans le cadre d'un modèle SBM dynamique.3) Un algorithme exact pour la détection de rupture dans les séries temporelles, la méthode pruned exact linear time (PELT), est étendu pour faire de la détection de rupture dans des données de graphe dynamique selon le modèle dSBM.4 Le modèle dSBM est étendu ultérieurement pour faire de l'analyse de réseau textuel dynamique. Les réseaux sociaux sont un exemple de réseaux textuels: les acteurs s'échangent des documents (posts, tweets, etc.) dont le contenu textuel peut être utilisé pour faire de la classification et détecter la structure temporelle du graphe dynamique. Le modèle que nous introduisons est appelé dynamic stochastic topic block model (dSTBM). Ce manuscrit est organisé de la façon suivante.Dans le premier chapitre nous faisons état des principales notions de théorie des graphes et des propriétés connues des réseaux réels. Deux définitions formelles de graphe dynamique sont énoncées. Ensuite, nous présentons les principaux modèles génératifs existants pour les graphes (statiques et dynamiques) et les méthodes d'estimation introduites dans la littérature pour ces modèles.Enfin, nous introduisons des outils statistiques (pas forcement liés à l'analyse de réseau) qui sont à la base de nos travaux.Dans le deuxième chapitre, deux versions du modèle dSBM sont présentées pour l'analyse des réseaux dynamiques en temps discret. Une procédure d'inférence est ensuite détaillée. Elle vise à maximiser (de façon gloutonne) la vraisemblance intégrée des données complétées: ceci permet d'estimer les paramètres du modèle tout en sélectionnant simultanément le nombre de classes. Le troisième chapitre introduit une version du modèle dSBM pour l'analyse de graphes dynamiques en temps continu. La méthode proposée assure une forme de détection de rupture dans l'évolution temporelle de ce type de graphes. L'inférence repose sur une approche variationnelle classique dont une partie est basée sur le PELT.Le quatrième chapitre revient sur les graphes dynamiques en temps discret. Les réseaux dynamiques textuels sont pris en compte, le modèle dSTBM est présenté et une procédure d'inférence est détaillée. Un critère de sélection de modèle est enfin formellement dérivé.En conclusion chaque chapitre, nous conduisons des expériences sur des données simulées et réelles. Ces expériences nous servent à la fois à tester les points forts et les faiblesses de nos méthodes et à les comparer avec des approches concurrentes.

Graphs are mathematical structures very suitable to model interactions between objects or actors of interest.Several real networks such as communication networks, financial transaction networks, mobile telephone networks and social networks (Facebook, Linkedin, etc.) can be modeled via graphs. When observing a network, the time variable comes into play intwo different ways: we can study the time dates at which the interactions occur and/or the interaction time spans. This thesis only focuses on the first time dimension and each interaction is assumed to be instantaneous, for simplicity. Hence, the network evolution is given by the interaction time dates only. In this framework, graphs can be used in two different ways to model networks:1) Discrete time. A network is observed at several times and a graph is associated with each observation time. Two nodes of a graph are connected if one or more interactions occurred between them in the corresponding time frame. Thus, interactions are aggregated between two consecutive observation times and the exact interaction dates are lost. In this context, a dynamic network is represented by a sequence of graphs.2) Continuous Time. Several edges are allowed to connect the nodes of a graph at different times. One edge is uniquely associated with a pair of nodes and a time point. No aggregation is required and interaction times are never lost. Therefore, a dynamic network is represented by a single multiple graph whose edges are labeled by the interaction times.In this thesis both these perspectives are adopted, alternatively. We consider new unsupervised methods to cluster the nodes of a graph into groups of homogeneous connection profiles. In this manuscript, the node groups are assumed to be time invariant to avoid possible identifiability issues. Moreover, the approaches that we propose aim to detect structural changes in the way the node clusters interact with each other. The building block of this thesis is the stochastic block model (SBM), a probabilistic approach initially used in social sciences. The standard SBM assumes that the nodes of a graph belong to hidden (disjoint) clusters and that the probability of observing an edge between two nodes only depends on their clusters. Since no further assumption is made on the connection probabilities, SBM is a very flexible model able to detect different network topologies (hubs, stars, communities, etc.).By adapting the block modeling perspective of SBM to dynamic graphs, the main contributions of this thesis are the following:1. We introduce a new extension of SBM for dynamic graphs. The proposed approach, called dSBM, adopts non homogeneous Poisson processes to model the interaction times between pairs of nodes in dynamic graphs, either in discrete or continuous time. The intensity functions of the processes only depend on the node clusters, in a block modeling perspective. Moreover, all the intensity functions share some regularity properties on hidden time intervals that need to be estimated.2. A recent estimation algorithm for SBM, based on the greedy maximization of an exact criterion (exact ICL) is adopted for inference and model selection in dSBM. To the best of our knowledge, this is the first time this algorithm is adopted for inference in dynamic stochastic block models.3. An exact algorithm for change point detection in time series, the "pruned exact linear time" (PELT) method is extended to deal with dynamic graph data modeled via dSBM. The approach we propose can be used for change point analysis in graph data. 4. A further extension of dSBM is developed to analyze dynamic networks with textual edges (like social networks, for instance). In this context, the graph edges are associated with documents exchanged between the corresponding nodes. The textual content of the documents can provide additional information about the dynamic graph topological structure. The new model we propose is called "dynamic stochastic topic block model" (dSTBM).This manuscript is organized as follows. In the first chapter, we pass through the main notions of graph theory and review some stylized facts about real networks. Two formal definitions of dynamic graph are provided. Then, the main existing generative models for static and dynamic random graphs are presented along with their associated inference procedures. Finally, some statistical tools not necessarily related with network analysis are described in detail since they are used in later chapters.In the second chapter, two versions of dSBM are introduced, both dealing with discrete time dynamic graphs. The corresponding inference procedure aims to maximize the complete data integrated log-likelihood, thus allowing us to learn the model parameters and select the number of clusters at the same time. In the third chapter, we model continuous time dynamic graphs via dSBM and focus on clustering and change point analysis in graph data. A standard variational approach is adopted for the inference and one step of the estimation algorithm relies on the PELT method.Finally, the fourth chapter introduces the dSTBM for discrete time dynamic graph with textual edges. The inference procedure is detailed and a model selection criterion is formally obtained.The last part of each chapter is devoted to experiments on both simulated and real data. These experiments allow us to highlight the features of the proposed approaches and to compare them with alternative methods.; Les graphes sont des structures mathématiques très adaptées pour modéliser les interactions parmi des objet/individus à étudier. De nombreux types de réseaux réels peuvent être modélisés à travers des graphes, tels que les réseaux de transport, les réseaux de transactions financières ou les réseaux sociaux comme Facebook ou Linkedin. Quand on observe un réseau d'interactions, le tempsentre en jeu de deux manières différentes: on peut étudier les instants auxquels les interactions ont lieu et les durées de ces interactions. Les travaux de cette thèse se limitent à la première dimension temporelle. Chaque interaction est donc considérée comme instantanée pour des raisons de simplicité. L'évolution du réseau repose ainsi sur les temps des interactions uniquement. Dans ce contexte, les graphes peuvent être utilisés de deux manières différentes pour modéliser les réseaux:1) Temps discret. Un réseau est observé à des instants différents et un graphe est associé à chacun de ces instants. Deux nœuds d'un graphe sont connectés si une ou plusieurs interactions entre eux sont observées dans le réseau à l'instant correspondant. Les interactions sont donc agrégées entre un instant d'observation et le suivant et les dates exactes des interactions sont perdues. Un réseau dynamique est enfin représenté par une séquence de graphes. 2)Temps continu. Plusieurs arcs connectent les nœuds d'un graphe. Chaque arc est donc uniquement associé à une paire de nœuds et à un instant temporel. Il n'y a pas d'agrégation temporelle dans ce cas et les instants exacts des interactions ne sont pas perdus. Le réseau dynamique est donc représenté par un seul graphe multiple dont les arcs sont étiquetés par les temps d'interaction. Dans cette thèse ces deux visions sont adoptées alternativement. Nous proposons de nouvelles méthodes d'apprentissage non supervisé qui visent à partitionner les sommets d'un graphe dynamique en classes homogènes au sens où les sommets d'une même classe ont des profils d'interaction similaires. Pour éviter des problèmes d'identifiabilité les groupes de nœuds ne changent pas dans le temps. Par ailleurs, les approches proposées visent à détecter des changements structurels dans la façon dont les groupes de nœuds interagissent entre eux. Le point de départ de cette thèse est le stochastic block model (SBM), une approche probabiliste initialement utilisée en sciences sociales. Dans la version standard du modèle, les nœuds d'un graphe sont répartis dans des classes et la probabilité d'apparition d'un arc entre deux nœuds dépend uniquement des classes auxquelles ils appartiennent. Comme aucune hypothèse n'étant faite sur les probabilités d'interaction, SBM est un modèle très flexible qui permet de capturer des structures topologiques différentes et variées (hubs, stars, communautés, etc.). Tout en gardant une approche de modélisation par blocs (comme dans SBM) dans le contexte des graphes dynamiques,les principales contributions de cette thèse sont les suivantes:1) Nous introduisons une nouvelle extension dynamique du SBM, appelée dSBM, qui utilise des processus de Poisson non homogènes pour modéliser les interactions parmi les paires de nœuds d'un graphe dynamique, en temps discret et continu. Les fonctions d'intensité des processus ne dépendent que des classes des nœuds comme dans SBM. De plus, ces fonctions d'intensité ont des propriétés de régularité sur des intervalles temporels qui sont à estimer, et à l'intérieur desquels les processus de Poisson redeviennent homogènes.2) Un récent algorithme d'estimation pour SBM, qui repose sur la maximisation d'un critère exact (ICL exacte) est ici adopté pour estimer les paramètres de dSBM et sélectionner simultanément le modèle optimal. notre connaissance, c'est la première fois que cet algorithme est utilisé dans le cadre d'un modèle SBM dynamique.3) Un algorithme exact pour la détection de rupture dans les séries temporelles, la méthode pruned exact linear time (PELT), est étendu pour faire de la détection de rupture dans des données de graphe dynamique selon le modèle dSBM.4 Le modèle dSBM est étendu ultérieurement pour faire de l'analyse de réseau textuel dynamique. Les réseaux sociaux sont un exemple de réseaux textuels: les acteurs s'échangent des documents (posts, tweets, etc.) dont le contenu textuel peut être utilisé pour faire de la classification et détecter la structure temporelle du graphe dynamique. Le modèle que nous introduisons est appelé dynamic stochastic topic block model (dSTBM). Ce manuscrit est organisé de la façon suivante.Dans le premier chapitre nous faisons état des principales notions de théorie des graphes et des propriétés connues des réseaux réels. Deux définitions formelles de graphe dynamique sont énoncées. Ensuite, nous présentons les principaux modèles génératifs existants pour les graphes (statiques et dynamiques) et les méthodes d'estimation introduites dans la littérature pour ces modèles.Enfin, nous introduisons des outils statistiques (pas forcement liés à l'analyse de réseau) qui sont à la base de nos travaux.Dans le deuxième chapitre, deux versions du modèle dSBM sont présentées pour l'analyse des réseaux dynamiques en temps discret. Une procédure d'inférence est ensuite détaillée. Elle vise à maximiser (de façon gloutonne) la vraisemblance intégrée des données complétées: ceci permet d'estimer les paramètres du modèle tout en sélectionnant simultanément le nombre de classes. Le troisième chapitre introduit une version du modèle dSBM pour l'analyse de graphes dynamiques en temps continu. La méthode proposée assure une forme de détection de rupture dans l'évolution temporelle de ce type de graphes. L'inférence repose sur une approche variationnelle classique dont une partie est basée sur le PELT.Le quatrième chapitre revient sur les graphes dynamiques en temps discret. Les réseaux dynamiques textuels sont pris en compte, le modèle dSTBM est présenté et une procédure d'inférence est détaillée. Un critère de sélection de modèle est enfin formellement dérivé.En conclusion chaque chapitre, nous conduisons des expériences sur des données simulées et réelles. Ces expériences nous servent à la fois à tester les points forts et les faiblesses de nos méthodes et à les comparer avec des approches concurrentes.

This thesis focuses on the statistical analysis of dynamic graphs, both defined in discrete or continuous time. We introduce a new extension of the stochastic block model (SBM) for dynamic graphs. The proposed approach, called dSBM, adopts non homogeneous Poisson processes to model the interaction times between pairs of nodes in dynamic graphs, either in discrete or continuous time. The intensity functions of the processes only depend on the node clusters, in a block modelling perspective. Moreover, all the intensity functions share some regularity properties on hidden time intervals that need to be estimated. A recent estimation algorithm for SBM, based on the greedy maximization of an exact criterion (exact ICL) is adopted for inference and model selection in dSBM. Moreover, an exact algorithm for change point detection in time series, the "pruned exact linear time" (PELT) method is extended to deal with dynamic graph data modelled via dSBM. The approach we propose can be used for change point analysis in graph data. Finally, a further extension of dSBM is developed to analyse dynamic net- works with textual edges (like social networks, for instance). In this context, the graph edges are associated with documents exchanged between the corresponding vertices. The textual content of the documents can provide additional information about the dynamic graph topological structure. The new model we propose is called "dynamic stochastic topic block model" (dSTBM).Graphs are mathematical structures very suitable to model interactions between objects or actors of interest. Several real networks such as communication networks, financial transaction networks, mobile telephone networks and social networks (Facebook, Linkedin, etc.) can be modelled via graphs. When observing a network, the time variable comes into play in two different ways: we can study the time dates at which the interactions occur and/or the interaction time spans. This thesis only focuses on the first time dimension and each interaction is assumed to be instantaneous, for simplicity. Hence, the network evolution is given by the interaction time dates only. In this framework, graphs can be used in two different ways to model networks. Discrete time […] Continuous time […]. In this thesis both these perspectives are adopted, alternatively. We consider new unsupervised methods to cluster the vertices of a graph into groups of homogeneous connection profiles. In this manuscript, the node groups are assumed to be time invariant to avoid possible identifiability issues. Moreover, the approaches that we propose aim to detect structural changes in the way the node clusters interact with each other. The building block of this thesis is the stochastic block model (SBM), a probabilistic approach initially used in social sciences. The standard SBM assumes that the nodes of a graph belong to hidden (disjoint) clusters and that the probability of observing an edge between two nodes only depends on their clusters. Since no further assumption is made on the connection probabilities, SBM is a very flexible model able to detect different network topologies (hubs, stars, communities, etc.)., Cette thèse porte sur l’analyse de graphes dynamiques, définis en temps discret ou continu. Nous introduisons une nouvelle extension dynamique du modèle a blocs stochastiques (SBM), appelée dSBM, qui utilise des processus de Poisson non homogènes pour modéliser les interactions parmi les paires de nœuds d’un graphe dynamique. Les fonctions d’intensité des processus ne dépendent que des classes des nœuds comme dans SBM. De plus, ces fonctions d’intensité ont des propriétés de régularité sur des intervalles temporels qui sont à estimer, et à l’intérieur desquels les processus de Poisson redeviennent homogènes. Un récent algorithme d’estimation pour SBM, qui repose sur la maximisation d’un critère exact (ICL exacte) est ici adopté pour estimer les paramètres de dSBM et sélectionner simultanément le modèle optimal. Ensuite, un algorithme exact pour la détection de rupture dans les séries temporelles, la méthode «pruned exact linear time» (PELT), est étendu pour faire de la détection de rupture dans des données de graphe dynamique selon le modèle dSBM. Enfin, le modèle dSBM est étendu ultérieurement pour faire de l’analyse de réseau textuel dynamique. Les réseaux sociaux sont un exemple de réseaux textuels: les acteurs s’échangent des documents (posts, tweets, etc.) dont le contenu textuel peut être utilisé pour faire de la classification et détecter la structure temporelle du graphe dynamique. Le modèle que nous introduisons est appelé «dynamic stochastic topic block model» (dSTBM).