Visite guidée de la distillerie de Scotch

François Pellegrini (LaBRI, Bordeaux)

jeudi 20 juin à 11h en salle 24-25/405, LIP6, Sorbonne Université

Le partitionnement de graphes est un problème très courant qui a de nombreuses applications dans le domaine de  l’informatique scientifique. Du fait de la taille croissante des problèmes à résoudre, de nombreuses mises en œuvre  parallèles d’algorithmes de partitionnement de graphes ont été proposées dans la littérature, que ce soit pour des multiprocesseurs à mémoire partagée ou des multi-ordinateurs à mémoire distribuée. Cet exposé présentera les  principales structures de données et les algorithmes mis en œuvre au sein des bibliothèques libScotch et  libPTScotch. Il se concentrera principalement sur les types d’algorithmes disponibles, plutôt que sur leurs détails  d’implémentation. Il abordera néanmoins quelques questions opérationnelles importantes, concernant la  reproductibilité et le multi-tâches.

De l’écosystème au graphe dynamique ou comment représenter la nature dans sa complexité.

Jacques Gignoux (iEES-Paris)

mardi 30 avril 2024 à 10h30 en salle 25-26/105, LIP6, Sorbonne Université

Transparents

L’écologie prétend étudier toutes les formes d’organisation du monde vivant, de la bactérie à la biosphère. Elle utilise pour cela le concept d’écosystème qui malgré sa simplicité autorise des représentations (graphiques, mathématiques, informatiques) efficaces très variées du monde qui nous entoure. Comme beaucoup de systèmes vivants, les écosystèmes sont qualifiés de systèmes complexes, susceptibles de présenter des propriétés émergentes comme la stabilité ou la résilience aux perturbations. Malheureusement, les définitions précise de l’émergence font défaut… ou sont beaucoup trop nombreuses pour être utilisables. Je montre qu’en se donnant une définition formelle d’un système possiblement complexe sous la forme d’un graphe dynamique, on peut arriver à la définition précise de 4 types d’émergence et des conditions dans lesquelles elles se manifestent. Sur cette base, on peut construire un simulateur généraliste applicable à l’écosystème et analysable en tant que système complexe avec des outils algorithmiques encore à définir, dont je proposerai un exemple. L’enjeu de ce travail est de fournir un cadre conceptuel permettant la comparaison des représentations/modèles d’écosystème et l’analyse de leurs propriétés émergentes.

Modèle de graphe hiérarchique pour la représentation et
l’analyse de la mobilité et du réseau maritime

Cyril Ray (École Navale / Arts et Métiers)

jeudi 28 mars 2024 à 14h en salle 25-26/105, LIP6, Sorbonne Université

La crise sanitaire et plus récemment la situation géopolitique internationale que nous traversons nous ont rappelé à quel point nos économies modernes étaient tributaires du transport international de marchandises en général et de la maritimisation des échanges internationaux en particulier (puisque 90% de ce transport s’effectuent par voie maritime). Le transport maritime est donc au coeur de nos économies globalisées. Désormais, à l’aide de nombreux capteurs, un large panel de données maritimes est collecté en continu, archivé, et exploité pour la réalisation de nombreuses applications (suivi des pêches, sécurisation de la navigation, planification de routes optimales, contrôle du respect des règles internationales, protection de la biodiversité…). Les bénéfices de cette numérisation de l’espace et de l’information maritime sont multiples. Elle offre de nombreuses opportunités pour appréhender, analyser, prédire les échanges maritimes par l’analyse des données. Durant cette présentation nous aborderons la conception d’un modèle de graphe de hiérarchique pour représenter les mobilités et le réseau de transport maritime. Le modèle est construit par agrégation de trajectoires sémantiques, elles-mêmes émergentes des données de localisation de navires. Le modèle de graphe se concentre sur les origines, destinations et points saillants des mobilités. Un lien entre les données géographiques et les nœuds du graphe est réalisé par indexation hexagonale hiérarchique. La présentation abordera également l’algorithme d’agrégation hiérarchique et les opérateurs de centralité et mesure d’évolution de la dynamique du graphe.

Road network structure and traffic patterns

Erwan Taillanter

mardi 14 mars 2024 à 10h30 en salle 24-25/405, LIP6, Sorbonne Université

Le trafic routier est un domaine habituellement associé aux sciences de l’ingénieur. Si des modèles physiques, basés sur des concepts d’hydrodynamique, ont été appliqué avec succès pour décrire le trafic sur des routes ou autoroutes, la question du trafic en milieu urbain, autrement plus complexe, est actuellement traitée principalement par le biais de simulations. Ces simulations s’avèrent malheureusement souvent imparfaites. Ceci provient du caractère chaotique du trafic routier, exacerbé sur un réseau urbain aux multiples facteurs exogènes (feux de circulation en tête), et où les intersections introduisent une forte corrélation entre les rues. Par conséquent, une simulation agent-basée, bien que réaliste à petite échelle, ne saurait décrire de façon satisfaisante l’évolution du système aux plus grandes échelles. Cette situation ressemble fortement à d’autres problèmes rencontrés dans le domaine de la physique, et en particulier dans le domaine des systèmes complexes. L’objet de ma thèse a donc été l’application d’outils issus de la physique statistique à la description du trafic routier en ville. La démarche générale est toujours de proposer des modèles « macroscopiques », ignorant la réalité individuelle des automobilistes pour se concentrer sur des grandeurs définies à l’échelle des rues ou du réseau entier. Cette discussion aura pour objectif de présenter deux de ces approches macroscopiques. D’une part, je présenterai un concept central en sciences du trafic urbain modernes, nommé Diagramme Fondamental Macroscopique (MFD). D’autre part, je présenterai des résultats suggérant que le trafic urbain se comporte comme un système physique subissant une transition de phase. Enfin, j’élargirai la discussion, en présentant des travaux tentant de combiner ces deux points de vues dans un point de vue cohérent.

Approches hybrides de détection d’anomalies dans les transactions financières.

Blaise Ngonmang

jeudi 11 janvier 2024 à 14h en salle 24-25/509, LIP6, Sorbonne Université

La fraude constitue un défi omniprésent dans divers secteurs tels que les services financiers et publics, engendrant d’importantes pertes financières pour les entreprises et institutions concernées. La prévention de la fraude représente ainsi un enjeu crucial. Cependant, la simple détection de la fraude ne suffit pas à atténuer ses conséquences; il est impératif de pouvoir la prouver opérationnellement. Ce séminaire explore des techniques de détection de fraudes basées sur des approches hybrides combinant l’apprentissage automatique et l’analyse de graphes. De plus, nous présentons des stratégies visant à faciliter l’interprétation des fraudes détectées.

Representing Edge Flows on Graphs via Sparse Cell Complexes

Josef Hoppe

vendredi 27 novembre 2023 à 11h en salle 24-25/405, LIP6, Sorbonne Université

Slides, codes, presentation at LoG

Obtaining sparse, interpretable representations of observable data is crucial in many machine learning and signal processing tasks. For data representing flows along the edges of a graph, an intuitively interpretable way to obtain such representations is to lift the graph structure to a simplicial complex: The eigenvectors of the associated Hodge-Laplacian, respectively the incidence matrices of the corresponding simplicial complex then induce a Hodge decomposition, which can be used to represent the observed data in terms of gradient, curl, and harmonic flows. In this paper, we generalize this approach to cellular complexes and introduce the flow representation learning problem, i.e., the problem of augmenting the observed graph by a set of cells, such that the eigenvectors of the associated Hodge Laplacian provide a sparse, interpretable representation of the observed edge flows on the graph. We show that this problem is NP-hard and introduce an efficient approximation algorithm for its solution. Experiments on real-world and synthetic data demonstrate that our algorithm outperforms state-of-the-art methods with respect to approximation error, while being computationally efficient.

How to assess and optimize the energy efficiency of microservices placement

Imane Taleb

vendredi 17 novembre 2023 à 14h en salle 26-00/124, LIP6, Sorbonne Université

Microservices are small, independent and scalable services used to build applications, offering flexibility and high-quality service. However, this model presents challenges in terms of network congestion, microservice placement, resource management and energy consumption. Based on an analysis revealing a lack of research on energy optimisation, this thesis focuses on assessing the energy efficiency of microservice placement, using graph partitioning techniques to optimise microservice placement across network architecture layers (Cloud, Fog, Edge).

Monotonicity on undirected networks

Sebastiano Vigna

mercredi 24 mai 2023 à 11h en salle 24-25/405, LIP6, Sorbonne Université

Slides

Is it always beneficial to create a new relationship (have a new follower/friend) in a social network? This question can be formally stated as a property of the centrality measure that defines the importance of the actors of the network. Score monotonicity means that adding an arc increases the centrality score of the target of the arc; rank monotonicity means that adding an arc improves the importance of the target of the arc relatively to the remaining nodes. It is known that most centralities are both score and rank monotone on directed, strongly connected graphs. In this paper, we study the problem of score and rank monotonicity for classical centrality measures in the case of undirected networks: in this case, we require that score, or relative importance, improve at both endpoints of the new edge. We show that, surprisingly, the situation in the undirected case is very different, and in particular that closeness, harmonic centrality, betweenness, eigenvector centrality, Seeley’s index, Katz’s index, and PageRank are not rank monotone; betweenness and PageRank are not even score monotone. In other words, while it is always a good thing to get a new follower, it is not always beneficial to get a new friend.

Continuous Average Straightness in Spatial Graphs

Vincent Labatut

vendredi 12 mai 2023 à 11h en salle 26-00/228 LIP6, Sorbonne Université

Slides

Straightness is a measure designed to characterize a pair of vertices in a spatial graph. In practice, it is often averaged over the whole graph, or a part of it. The standard approach consists in: 1) discretizing the graph edges, 2) processing the vertex-to-vertex Straightness considering the additional vertices resulting from this discretization, and 3) averaging the obtained values. However, this discrete approximation can be computationally expensive on large graphs, and its precision has not been clearly assessed. In this work, we adopt a continuous approach to average the Straightness over the edges of spatial graphs. This allows us to derive 5 distinct measures able to characterize precisely the accessibility of the whole graph, as well as individual vertices and edges. Our method is generic and could be applied to other measures designed for spatial graphs. We perform an experimental evaluation of our continuous average Straightness measures, and show how they behave differently from the traditional vertex-to-vertex ones. Moreover, we also study their discrete approximations, and show that our approach is globally less demanding in terms of both processing time and memory usage.

Penser l’ingénierie et ses outils informatiques dans des contextes de soutenabilité forte : le cas de l’analyse environnementale en conception

Lou Grimal

mardi 9 mai 2023 à 11h en salle 26-00/428 LIP6, Sorbonne Université

Une transition des systèmes socio-techniques semble être nécessaire afin de limiter le dépassement des limites planétaires. L’ingénierie, activité influencée par le contexte historique et épistémologique de son époque, peut être un levier pour cette transition. Ma thèse a permis de proposer un cadre théorique pour comprendre comment l’ingénierie peut exister dans des contextes de soutenabilité forte et explorer des outils informatiques qui peuvent être déployés dans ces contextes. Ce cadre est composé de 4 caractéristiques (éthique, objectif, démarche, expertise) et adresse le niveau de l’ingénierie et le niveau des interactions entre l’ingénieur et ses outils informatiques. La méthodologie Value Sensitive Design a été mise en œuvre pour explorer ce cadre théorique. Deux expérimentations ont été conduites pour tester une première médiatisation de la permaingénierie dans un outil informatique – outil mettant en œuvre une démarche d’analyse environnementale collaborative. Ces expérimentations ont permis de montrer un besoin de cadre conceptuel pour une ingénierie en contexte de soutenabilité forte et un manque de pratique des acteurs exprimant ce besoin. Trois contributions ont été identifiées : (1) la formalisation du cadre de permaingénierie, (2) l’approche par les interactions humains-machines pour adresser les questions de transitions culturelles et changement de valeurs, (3) l’impossibilité de transformer un outil d’ingénierie de soutenabilité faible en outil de soutenabilité forte.

Hearing the shape of a robotic arena: Spectral shape analysis by Kilobots

Main author and presenter: Leo Cazenille
Other authors: Nicolas Lobato-Dauzier, Alessia Loi, Mika Ito, Olivier Marchal, Nathanael Aubert-Kato, Nicolas Bredeche, Anthony J. Genot

April 18th, 2023, 11am
Room: 24-25/405

Biological swarms have showcased their extraordinary capabilities in tackling geometric challenges by employing limited perception and mobility. They achieve this feat by internally diffusing information to bridge the gap between local and global scales, ultimately facilitating collective consensus and decision-making, even when individual agents only have access to local information. In this study, we strive to adapt this paradigm to robotic swarms, which consist of small robots with constrained sensing and computational abilities.

Our bio-inspired approach leverages spectral shape analysis, enabling the robotic swarms to identify the shape of a given arena. By estimating the second eigenvalue of the Laplacian collectively through information exchange, the robots can effectively obtain a fingerprint of the arena’s geometry. This metric, known as algebraic connectivity, proves invaluable in the context of swarm-based problem-solving and coordination.

To evaluate the performance of our proposed method, we conducted experiments involving 25 real robots as well as simulations using Kilombo, a state-of-the-art simulator for kilobots. Our objective was to assess the efficacy of our approach by attempting to classify a set of 8 shapes with varying geometric properties. The results of these experiments and simulations indicate that the diffusion-based spectral analysis can indeed empower robotic swarms to accurately sense and classify the geometry of their environment.

In conclusion, our innovative approach offers a promising avenue for advancing swarm-based problem-solving and coordination by drawing inspiration from the remarkable capabilities of biological swarms in addressing geometric challenges with limited perception and mobility.

(Presentation in French with slides in English).

Compact representation of distances in sparse graphs: a tour around 2-hop labelings

Laurent Viennot

mercredi 25 janvier 2023, 26-00/332 LIP6, Sorbonne Université

Slides

A 2-hop labeling (a.k.a. hub labeling) consists in assigning to each node of a graph a small subset of nodes called hubs so that any pair of nodes have a common hub lying on a shortest path joining them. Such labelings appeared to provide a very efficient representation of distances in practical road network where surprisingly small hub sets can be computed. A graph parameter called skeleton dimension allows to explain this behaviour. Connecting any two nodes through a common hub can be seen as a 2-hop shortest path in a super-graph of the original graph. A natural extension is to consider more hops and is related to the notion of hopsets introduced in parallel computation of shortest paths. Surprisingly, a 3-hop construction leads to a data-structure for representing distances which is asymptotically both smaller and faster than 2-hop labeling in graphs of bounded skeleton dimension. Another natural question is to ask whether 2-hop labelings can be efficient more generally in sparse graphs. Unfortunately, this is not the case as there exists bounded degree graphs that require quasi-linear average hub set size. The construction of such difficult graphs is related to the construction of dense graphs with n nodes that can be decomposed into n induced matchings as introduced by Ruzsa and Szemerédi in the seventies.

Efficient data stream mining

Maroua Bahri

June 27th, 2022, 11am

Room : 24-25/405

Slides

Data streams pose several challenges for learning algorithms, including mainly, but not limited to, restricted resources (in terms of memory and processing time), high-dimensionality, and concept drift constraints. To process these evolving data, we need efficient and accurate techniques and strategies, such as window models, summarization techniques, and other manners to restrict the storage to a part of — and/or synopsis information from — the stream instead of maintaining it in its entirety. This talk will present how such challenges can be addressed and how we can reduce machine learning algorithms’ resource costs while maintaining good accuracy.

The Role of Network Topology on Community-aware Centrality Measures

Stephany Rajeh

April 4th, 2022, 11am
Room : 24-25/405

While there is a great deal of work on designing centrality measures, the mainstream does not exploit the network’s community structure. Nevertheless, communities are pervasive in many real-world networks. A community is generally apprehended as a group of nodes densely connected between each other and sparsely connected with other nodes. As communities play a significant role in understanding how nodes behave in networks, a research area concerned with the relation between community structure and the importance of nodes has recently emerged in network science. These works have shown that incorporating community structure information allows designing more effective centrality measures. We refer to them as “community-aware” centrality measures. In this talk, we shed light on how classical (i.e., community-agnostic) centrality measures relate to community-aware centrality measures given a network’s macroscopic and mesoscopic topology. Then, we show the subtility of using these measures in different dynamic models, namely the Susceptible-Infected-Recovered (SIR) model and the Linear Threshold (LT) model. Additionally, as there are plenty of works to detect overlapping communities, few scientists make use of the overlapping community structure to identify critical nodes. Indeed, nodes may belong to several communities in many situations, indicating an overlapping community structure. We propose a framework to target influential nodes in networks with an overlapping community structure inspired by the concept of vitality. Finally, ascribable to the significance of communities in real-world networks, we present a backbone extraction method that maintains the network’s modularity while essentially reducing its  original size.

Randomized reference models for complex networks

Christian Lyngby Vestergaard, PhD

March 25th, 2022, 11am
Room : 26-00/332

Video: https://nuage.lip6.fr/s/db5bsrFMssEAoQD

Many dynamical systems can be successfully analyzed by representing them as networks. Empirically measured networks and dynamic processes that take place in these situations show heterogeneous, non-Markovian, and intrinsically correlated topologies and dynamics. This makes their analysis particularly challenging. Randomized reference models (RRMs) have emerged as a general and versatile toolbox for studying such systems. Defined as random networks with given features constrained to match those of an input (empirical) network, they may for example be used to identify important features of empirical networks and their effects on dynamical processes unfolding in the network. RRMs are typically implemented as procedures that reshuffle an empirical network, making them very generally applicable. However, the effects of most shuffling procedures on network features remain poorly understood, rendering their use non-trivial and susceptible to misinterpretation. I will describe a unified framework for the important class of RRMs generated by uniform shuffling procedures, which we by analogy to statistical physics will name microcanonical RRMs (MRRMs). MRRMs constrain chosen features to take exactly the same value as in the empirical network but are otherwise maximally random. Our framework lets us build a taxonomy of MRRMs that orders them and deduces their effects on important network features. It additionally tells us how we may generate new MRRMs by composition of existing ones. I will show examples of how the framework can be applied to unravel the influence of different features of an empirical network of mobile-phone calls on the spread of information and to characterize structural circuit motifs in the brain wiring diagrams (connectomes) of small animals. If time permits, I will finally discuss how we may use graph compression techniques to alleviate the statistical problems associated to classical null hypothesis testing for network motif discovery.
Reference: hal.archives-ouvertes.fr/hal-01817633v4

Complex Systems approach to the emergence of socio-economic phenomena

Yérali Gandica

February 3rd 2022, 2pm; Room 26-00/332

Slides

In this talk, I will present some of my publications using Complex Systems approaches to understand the emergence of socio-economic phenomena. Complex System science aims to study the phenomena that emerge from the interactions between the constituents and, thus, cannot be understood by studying a singular, isolated component. The field has incorporated concepts and methods derived from many areas, ranging from statistical physics and biology to economics and sociology, which, in a constant process of cross-fertilization, have given rise to new types of questions framed into the field of Complex Systems. The study of interacting particle systems has, for along time, been an essential subject of physics. The use of statistical methods has allowed for significant advances in this area by providing a bridge between the microscopic interactions and the sizeable collective behaviour of the system. The application of the methods of statistical physics to social phenomena, where the interacting particles are now interacting human beings, has proven to be very fruitful in allowing for the understanding of many features of social collective behaviour. The success of the statistical physics approaches to explain social data is currently attracting much interest, as demonstrated by the rapidly increasing number of publications in the field from both natural and social scientists. Some of the works that I will present are based on simulations, while some others are based on real data. In some cases, the comparison between simulations and real data is achieved. I will also explain some works in progress and projects for the incoming medium and long term to give a flavour about the scientific path that I plan, to illustrate the coherence of my scientific line of research.

Random Spanning Forests on Graphs for Fast Laplacian-Based Computations

Nicolas Tremblay

lundi 17 janvier 2022, LIP6, Sorbonne Université

Graphs are ubiquitous tools to represent networks, may they be networks modeling data from neurosciences, sociology, molecular biology, chemistry, etc. A cornerstone of the analysis of graphs is the Laplacian matrix L that encodes their structure. From a linear algebra point-of-view, the analysis of L offers fundamental insights on key properties of the graph: the diffusion speed of an information or a disease on a network, the vulnerability of a network to targeted or random attacks, the redundancy of certain parts of the network, the network’s structure in more or less independent modules, are all examples of characteristics of a network one may extract from the Laplacian matrix.

In this work, we concentrate on two specific problems that often arise in the context of graph-based data: i/ compute inverse traces of the form Tr( (L+qI)^(-1) ), ii/ compute smoothing operations of the form (L+qI)^(-1) y where q>0 and y some vector defined over the nodes of the graph. These two problems arise in many well-known graph-based algorithms, such as semi-supervised learning, label propagation, graph Tikhonov regularization, graph inpainting, etc.

In the context of large graphs, the required inverse which scales as O(n^3) in the worst-case, is often too expensive in practice. Many approaches have been developed in the state-of-the-art to circumvent this problem: polynomial approximation and (preconditioned) conjugate gradient are the two most well-known.

In this work, we develop a new class of techniques based on random spanning forests. We show that these forests are natural candidates to provide original, efficient, and easy-to-implement estimators.

This is joint work with Pierre-Olivier Amblard, Luca Avena, Simon Barthelmé, Alexandre Gaudillière and Yusuf Yigit Pilavci

Presentation by Esteban Bautista on Fractional PageRank

Esteban Bautista

Lundi 25 Janvier 2021, à 14h Présentiel: salle 25-26-105,  Revoir La Présentation:

Slides

Graph-Based Semi-Supervised Learning (G-SSL) techniques learn from both labelled and unlabelled data to build better classifiers. This classification paradigm has received considerable attention since modern applications allow to collect large amounts of unlabelled but structured data, naturally encoded by a graph, in a relatively easy and inexpensive manner, while annotated data is expensive to obtain.  Despite successes, the performance of G-SSL techniques can still be improved, particularly in challenging data settings or unbalanced scenarios. To address such limitations, I will present a novel G-SSL method based on the positive γ -th powers of the graph Laplacian, referred to as the Lγ-PageRank method. I will present a theoretical analysis of the new method, showing that (i) for γ < 1, it extends the standard PageRank algorithm to Lévy processes: where random walkers can now perform far-distant jumps in a single step; and (ii) for γ > 1, it classifies data on signed graphs: where nodes belonging to one same class are more likely to share positive edges while nodes from different classes are more likely to be connected with negative edges. I will also show the existence of an optimal Laplacian power maximizing performance, for which I will propose an algorithm for its automatic estimation. Lastly, I will show the significant classification improvements allowed by the proposed approach on several real-world datasets commonly used for classification.  

Temporal Cliques Admit Sparse Spanners

Jason Schoeters

Mardi 10 Novembre 2020, à 11h en salle 25-26/105, Jussieu

Let G=(V,E) be an undirected graph on n vertices and λ:E →2^N a mapping that assigns to every edge a non-empty set of positive integer labels. These labels can be seen as discrete times when the edge is present. Such a labeled graph {\cal G}=(G,λ) is said to be temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar (STOC 2000) asked whether, given such a temporal graph, a sparse subset of edges can always be found whose labels suffice to preserve temporal connectivity—a temporal spanner. Axiotis and Fotakis (ICALP 2016) answered negatively by exhibiting a family of Θ(n^2)-dense temporal graphs which admit no temporal spanner of density o(n^2). The natural question is then whether sparse temporal spanners can always be found in some classes of dense graphs. In this paper, we answer this question affirmatively, by showing that if the underlying graph G is a complete graph, then one can always find temporal spanners of density O(n log n). The best known result for complete graphs so far was that spanners of density (n choose 2)−⌊n/4⌋=O(n^2) always exist. Our result is the first positive answer as to the existence of o(n^2) sparse spanners in adversarial instances of temporal graphs since the original question by Kempe et al., focusing here on complete graphs. The proofs are constructive and directly adaptable as an algorithm.

Modèles et algorithmes pour les graphes dynamiques

Mathilde Vernet

Jeudi 22 Octobre 2020 à 11h en salle 25-26/105, Jussieu

Slides

Les problèmes de graphes ont été largement étudiés dans le cas des graphes statiques. Cependant, ces graphes ne permettent pas de prendre en compte la dimension temporelle, qui est souvent une donnée importante pour les situations à modéliser. Les graphes dynamiques viennent combler ces lacunes en permettant de modéliser des évolutions dans le temps. On peut alors s’interroger sur ces mêmes problèmes de graphes dans un contexte dynamique. Cela passe d’abord par la définition du modèle de graphes dynamiques le plus approprié et la modélisation précise du problème sur ces graphes. Lorsque le problème ne peut pas être résolu efficacement en appliquant directement des méthodes connues sur les graphes statiques, il faut alors concevoir un algorithme de résolution spécifique aux graphes dynamiques et l’analyser théoriquement et expérimentalement. En suivant cette démarche, l’objectif de cette thèse est de s’interroger sur l’extension aux graphes dynamiques des problèmes bien connus sur les graphes statiques. Ce travail s’intéresse à plusieurs problèmes de graphes en contexte dynamique en se focalisant sur les aspects algorithmiques et en s’abstrayant des domaines d’applications. Nous nous intéressons d’abord aux problèmes de flot dans les graphes dynamiques et proposons en particulier pour le problème du flot de cout minimum un algorithme polynomial permettant de résoudre le problème de façon optimale pour un modèle de graphe dynamique spécifique. Des problèmes liés à la connexité des graphes dynamiques sont aussi étudiés. Les composantes connexes persistantes, extension des composantes connexes aux graphes dynamiques, traduisent la connexité d’un ensemble de nœuds pendant un certain nombre de pas de temps consécutifs. De façon analogue à la notion de maximalité des composantes connexes dans un graphe statique, une notion de dominance entre composantes connexes persistantes est définie. Un algorithme polynomial permettant d’identifier toutes les composantes connexes persistantes non dominées est proposé. Plusieurs extensions à la définition de composantes connexes persistantes sont étudiées. Nous proposons enfin des extensions possibles du problème de Steiner aux graphes dynamiques. Nous nous concentrons sur un cas particulier et montrons la NP-complétude de ce problème.