Search

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.

The numerical surge that characterizes the modern scientific era led to the rise of new kinds of data united in one common immoderation: the simultaneous acquisition of a large number of measurable quantities. Whether coming from DNA microarrays, mass spectrometers, or nuclear magnetic resonance, these data, usually called high-dimensional, are now ubiquitous in scientific and technological worlds. Processing these data calls for an important renewal of the traditional statistical toolset, unfit for such frameworks that involve a large number of variables. Indeed, when the number of variables exceeds the number of observations, most traditional statistical techniques become inefficient.First, we give a brief overview of the statistical issues that arise with high-dimensional data. Several popular solutions are presented, and we present some arguments in favor of the method utilized and advocated in this thesis: Bayesian model uncertainty. This chosen framework is the subject of a detailed review that insists on several recent developments.After these surveys come three original contributions to high-dimensional model selection. A new algorithm for high-dimensional sparse regression called SpinyReg is presented. It compares favorably to state-of-the-art methods on both real and synthetic data sets. A new data set for high-dimensional regression is also described: it involves predicting the number of visitors in the Orsay museum in Paris using bike-sharing data. We focus next on model selection for high-dimensional principal component analysis (PCA). Using a new theoretical result, we derive the first closed-form expression of the marginal likelihood of a PCA model. This allows us to propose two algorithms for model selection in PCA. A first one called globally sparse probabilistic PCA (GSPPCA) that allows to perform scalable variable selection, and a second one called normal-gamma probabilistic PCA (NGPPCA) that estimates the intrinsic dimensionality of a high-dimensional data set. Both methods are competitive with other popular approaches. In particular, using unlabelled DNA microarray data, GSPPCA is able to select genes that are more biologically relevant than several popular approaches.; Le déferlement numérique qui caractérise l’ère scientifique moderne a entrainé l’apparition de nouveaux types de données partageant une démesure commune : l’acquisition simultanée et rapide d’un très grand nombre de quantités observables. Qu’elles proviennent de puces ADN, de spectromètres de masse ou d’imagerie par résonance nucléaire, ces bases de données, qualifiées de données de grande dimension, sont désormais omniprésentes, tant dans le monde scientifique que technologique. Le traitement de ces données de grande dimension nécessite un renouvellement profond de l’arsenal statistique traditionnel, qui se trouve inadapté à ce nouveau cadre, notamment en raison du très grand nombre de variables impliquées. En effet, confrontée aux cas impliquant un plus grand nombre de variables que d’observations, une grande partie des techniques statistiques classiques est incapable de donner des résultats satisfaisants.Dans un premier temps, nous introduisons les problèmes statistiques inhérents aux modèles de données de grande dimension. Plusieurs solutions classiques sont détaillées et nous motivons le choix de l’approche empruntée au cours de cette thèse : le paradigme bayésien de sélection de modèles. Ce dernier fait ensuite l’objet d’une revue de littérature détaillée, en insistant sur plusieurs développements récents.Viennent ensuite trois chapitres de contributions nouvelles à la sélection de mo- dèles en grande dimension. En premier lieu, nous présentons un nouvel algorithme pour la régression linéaire bayésienne parcimonieuse en grande dimension, dont les performances sont très bonnes, tant sur données réelles que simulées. Une nouvelle base de données de régression linéaire est également introduite : il s’agit de prédire la fréquentation du musée d’Orsay à l’aide de données vélibs. Ensuite, nous nous penchons sur le problème de la sélection de modèles pour l’analyse en composantes principales (ACP). En nous basant sur un résultat théorique nouveau, nous effectuons les premiers calculs exacts de vraisemblance marginale pour ce modèle. Cela nous permet de proposer deux nouveaux algorithmes pour l’ACP parcimonieuse, un premier, appelé GSPPCA, permettant d’effectuer de la sélection de variables, et un second, appelé NGPPCA, permettant d’estimer la dimension intrinsèque de données de grande dimension. Les performances empiriques de ces deux techniques sont extrêmement compétitives. Dans le cadre de données d’expression ADN notamment, l’approche de sélection de variables proposée permet de déceler sans supervision des ensembles de gènes particulièrement pertinents.

The numerical surge that characterizes the modern scientific era led to the rise of new kinds of data united in one common immoderation: the simultaneous acquisition of a large number of measurable quantities. Whether coming from DNA microarrays, mass spectrometers, or nuclear magnetic resonance, these data, usually called high-dimensional, are now ubiquitous in scientific and technological worlds. Processing these data calls for an important renewal of the traditional statistical toolset, unfit for such frameworks that involve a large number of variables. Indeed, when the number of variables exceeds the number of observations, most traditional statistical techniques become inefficient.First, we give a brief overview of the statistical issues that arise with high-dimensional data. Several popular solutions are presented, and we present some arguments in favor of the method utilized and advocated in this thesis: Bayesian model uncertainty. This chosen framework is the subject of a detailed review that insists on several recent developments.After these surveys come three original contributions to high-dimensional model selection. A new algorithm for high-dimensional sparse regression called SpinyReg is presented. It compares favorably to state-of-the-art methods on both real and synthetic data sets. A new data set for high-dimensional regression is also described: it involves predicting the number of visitors in the Orsay museum in Paris using bike-sharing data. We focus next on model selection for high-dimensional principal component analysis (PCA). Using a new theoretical result, we derive the first closed-form expression of the marginal likelihood of a PCA model. This allows us to propose two algorithms for model selection in PCA. A first one called globally sparse probabilistic PCA (GSPPCA) that allows to perform scalable variable selection, and a second one called normal-gamma probabilistic PCA (NGPPCA) that estimates the intrinsic dimensionality of a high-dimensional data set. Both methods are competitive with other popular approaches. In particular, using unlabelled DNA microarray data, GSPPCA is able to select genes that are more biologically relevant than several popular approaches.; Le déferlement numérique qui caractérise l’ère scientifique moderne a entrainé l’apparition de nouveaux types de données partageant une démesure commune : l’acquisition simultanée et rapide d’un très grand nombre de quantités observables. Qu’elles proviennent de puces ADN, de spectromètres de masse ou d’imagerie par résonance nucléaire, ces bases de données, qualifiées de données de grande dimension, sont désormais omniprésentes, tant dans le monde scientifique que technologique. Le traitement de ces données de grande dimension nécessite un renouvellement profond de l’arsenal statistique traditionnel, qui se trouve inadapté à ce nouveau cadre, notamment en raison du très grand nombre de variables impliquées. En effet, confrontée aux cas impliquant un plus grand nombre de variables que d’observations, une grande partie des techniques statistiques classiques est incapable de donner des résultats satisfaisants.Dans un premier temps, nous introduisons les problèmes statistiques inhérents aux modèles de données de grande dimension. Plusieurs solutions classiques sont détaillées et nous motivons le choix de l’approche empruntée au cours de cette thèse : le paradigme bayésien de sélection de modèles. Ce dernier fait ensuite l’objet d’une revue de littérature détaillée, en insistant sur plusieurs développements récents.Viennent ensuite trois chapitres de contributions nouvelles à la sélection de mo- dèles en grande dimension. En premier lieu, nous présentons un nouvel algorithme pour la régression linéaire bayésienne parcimonieuse en grande dimension, dont les performances sont très bonnes, tant sur données réelles que simulées. Une nouvelle base de données de régression linéaire est également introduite : il s’agit de prédire la fréquentation du musée d’Orsay à l’aide de données vélibs. Ensuite, nous nous penchons sur le problème de la sélection de modèles pour l’analyse en composantes principales (ACP). En nous basant sur un résultat théorique nouveau, nous effectuons les premiers calculs exacts de vraisemblance marginale pour ce modèle. Cela nous permet de proposer deux nouveaux algorithmes pour l’ACP parcimonieuse, un premier, appelé GSPPCA, permettant d’effectuer de la sélection de variables, et un second, appelé NGPPCA, permettant d’estimer la dimension intrinsèque de données de grande dimension. Les performances empiriques de ces deux techniques sont extrêmement compétitives. Dans le cadre de données d’expression ADN notamment, l’approche de sélection de variables proposée permet de déceler sans supervision des ensembles de gènes particulièrement pertinents.

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.