La détection de communautés dans les réseaux est aujourd'hui un domaine ayant donné lieu à une abondante littérature. Depuis les travaux de Girvan et Newman en 2002, des centaines de travaux ont été menés sur le sujet, notamment la proposition d'un nombre important d'algorithmes de plus en plus élaborés. Cependant, la majorité de ces travaux portent sur des communautés statiques dans des réseaux statiques. Or, beaucoup de réseaux de terrains sont en fait dynamiques, ils évoluent au cours du temps. L'apport principal de cette thèse est donc la conception d'un algorithme de détection de communautés dynamiques sur des réseaux temporels. Le manuscrit est découpé en quatre sections : La première est un état de l'art, où sont passés en revu les méthodes existantes pour la détection de communauté, statiques, dynamiques, avec et sans recouvrement. La seconde est la présentation de la solution que nous proposons : iLCD, un framework pour la détection de communautés dynamiques dans les réseaux temporels, ainsi que deux implémentations de ce framework. La troisième partie présente les travaux effectués pour valider iLCD sur le plan statique, c'est à dire valider que les communautés trouvées sont pertinentes comparées à d'autres algorithmes existant sur des réseaux statiques. Pour ce faire, nous proposons des idées originales, afin de pouvoir comparer des méthodes sur des graphes réels. Enfin, la dernière partie est consacrée à la validation de l'aspect dynamique d'iLCD. En effet, la dynamique introduit des données supplémentaires : l'apparition et la disparition de communautés, leur évolution en continue, ainsi que des opérations complexes, telles que la fusion ou la division de communautés au cours du temps. Ce sont ces aspects qui sont validés ici, en étudiant en détail les résultats obtenus sur des réseaux réels.

Les technologies modernes permettent d'avoir des renseignements toujours plus précis sur les interactions entre individus. Dans ce contexte, la collaboration SocioPatterns a permis de développer une infrastructure mesurant, avec une très grande résolution temporelle, la proximité face-à-face d'individus volontaires, portant des badges de radio-identi cation. Cette infrastructure a été déployée dans divers contextes, tels que des conférences scienti ques, un musée, une école ou encore un service hospitalier. La simple analyse de ces données représente un enjeu majeur pour l'étude de la dynamique humaine et soulève des questions aussi fondamentales que la recherche d'outils et de techniques d'analyse adaptés. Cette thèse présente la caractérisation statistique de la dynamique de proximité physique, mise en relation avec le contexte et les autres métadonnées disponibles, telles que l'âge, le sexe des individus, ou bien la structure de leurs réseaux sociaux virtuels. Si la structure des contacts diff ère considérablement selon le contexte, les distributions empiriques des durées des interactions et entre interactions sont très similaires. Un modèle individu-centré, présenté dans cette thèse, propose des règles d'interactions microscopiques simples susceptibles de donner lieu à cette structure macroscopique complexe des temps d'interaction. Enfin, la caractérisation de la dynamique des contacts entre individus constitue une étape cruciale pour comprendre les mécanismes de propagation de maladies telles que la grippe dans une population. Les données de proximité humaine ont permis d'étudier la quantité d'informations nécessaires sur la dynamique des contacts pour la construction de modèles épidémiologiques de contagion. De tels modèles permettent de mieux estimer a priori l'impact de stratégies de santé publique telles que la fermeture de classes et les vaccinations ciblées.

Le maintien de la morphologie et la production des forces par les cellules sont possibles grâce au cytosquelette, constitué de trois types de polymères protéiques dont les microfilaments d’actine. Les filaments d’actine s’organisent en différentes architectures, dont l’assemblage et le désassemblage sont étroitement contrôlés dans le temps et l’espace. En effet, une des caractéristiques d’un filament d’actine est son vieillissement, par l’hydrolyse progressive de l’ATP au sein des sous-unités. Pour assurer un renouvellement continu de l’ actine celle-ci doit donc être recyclée. Lorsque l’assemblage et désassemblage se compensent, les architectures d’actine sont alors dans un état stationnaire dynamique, dans lequel la concentration demonomères d’actine est perpétuellement renouvelée. Le désassemblage permet également de maintenir un réservoir important d’actine monomérique polymérisable, pour répondre rapidement aux besoins cellulaires. Le lamellipode, organe moteur de la cellule, est essentiellement composé d’unfeuillet fin mais très dense d’actine dendritique ainsi que de protéines régulatrices. Une protéine essentielle dans le turnover rapide du lamellipode est l’ADF/Cofiline. Elle est responsable du désassemblage des filaments âgés par fragmentation et pardébranchement. Jusqu’à présent, les études portaient le plus souvent sur les mécanismes microscopiques, à l’échelle du filament individuel. Or, pour comprendre la dynamique des réseaux branchés notamment au cours de la motilité cellulaire, il nous faut comprendre le désassemblage collectif et macroscopique du réseau d’actine dendritique. En combinant des milieux de motilité reconstitués à partir de protéinespurifiées à une nouvelle technique de micro-structuration de surfaces, j’ai pu reconstituer in vitro des réseaux dendritiques semblables au lamellipode. Ainsi, j’ai exploré au cours de ma thèse les paramètres qui contrôlent leur désassemblage macroscopique. Il en ressort que le désassemblage des réseaux dépend de leur architecture (densité) et de leur géométrie (taille) : les réseaux denses ou étendus sont moins efficacement désassemblés et restent cohésifs plus longtemps. Des modélisations montrent que c’est la déplétion locale en ADF/Cofiline autour du réseau d’actine qui semble responsable des effets observés. De plus, les réseaux constitués de densités d’actine hétérogènes acquièrent une directionnalité, qui peut être modulée par le désassemblage sélectif par ADF/Cofiline. Parallèlement, ces études ont permis de déterminer que pour avoir un réseau à l’état dynamiquestationnaire (ou à l’équilibre), il fallait atteindre un certain ratio d’ADF/Cofiline par actine. Ce travail a permis d’aller plus loin que les études fondamentales sur la fragmentation de filaments d’actine individuels, à l’échelle microscopique, et d’établir deux nouveaux paramètres qui contrôlent le désassemblage de réseaux d’actine dendritique à l’échelle macroscopique / Cells maintain their morphology and produce forces thanks to the cytoskeleton, which is composed of three types of protein polymers, amongst which the actin microfilaments. Actin filaments assemble into diverse architectures, which assembly and disassembly is tightly controlled in space and time. Indeed, the progressive hydrolysis of ATP in the monomers causes the actin filaments to age. Thus, actin needs to be recycled. When assembly and disassembly compensate, different actin architectures are in a dynamic steady state, in which the pool of actin monomers is renewed. Disassembly of actin structures also maintains a large reservoir of polymerization-ready monomers ready to assemble when needed by the cell.The lamellipodium is the locomotory organelle of the cell, and is made of a thin yet very dense sheet of dendritic actin network, with regulatory proteins. A pivotal protein is ADF/Cofilin, which is responsible of the disassembly of old actin filaments by fragmentation and debranching. To date, there have been extensive studies about the microscopic mechanisms, but if one wants to understand cell motility, one must decipher the collective and macroscopic disassembly of the dendritic actin network.By combining motility media reconstituted from purified proteins, and a new surface micro-patterning technique, I was able to reconstitute lamellipodium-like dendritic networks in vitro. During this thesis I explored the parameters that control the macroscopic disassembly of these networks. This work shows that the disassembly of dendritic actin networks depends on their architecture (density) and geometry (size): dense or extended networks are less efficiently disassembled and remain cohesive longer. Simulations show that these effects can be explains by a local depletion of ADF/Cofilin in the volume surrounding the network. Besides, networks of heterogeneous densities acquire directionality. This steering is modulated by selective disassembly of the networks by ADF/Cofilin. In parallel, these studies established a ratio at which networks are at a dynamic steady state.This work goes further than the fundamentally important studies about fragmentation of individual actin filaments, and establishes new parameters that control the disassembly of dendritic actin at the macroscopic scale.

Les réseaux sont des modèles qui nous permettent de comprendre les relations entre éléments du monde réel. Une grande quantité de réseaux sont dynamiques, c'est-à-dire que leur connexité change au cours du temps. Comprendre les changements de connexité signifie comprendre les interactions entre les éléments de systèmes complexes: comment se forment les relations sociales et commerciales, comment sont transmis les signaux entre les régions du cerveau, comment s'organisent les réseaux trophiques après des catastrophes environnementales. Au-delà de ce que nous permettent la technologie et les algorithmes d'analyses, l'homme dispose d'une capacité unique pour comprendre et interpréter des informations : la vision et la cognition. Cette thèse développe et examine des moyens pour explorer les réseaux dynamiques d'une manière interactive et visuelle. Je propose des techniques pour déplier la complexité des réseaux, avec le but de les rendre compréhensibles, de les voir à partir de perspectives différentes, d'examiner leurs composantes. Déplier des réseaux est une métaphore, comme la création des cartes bidimensionelles d'objets tridimensionnels comme la Terre: chaque méthode de projection a comme résultat une carte différente qui permet de voir des relations différentes entre la taille des continents et des océans, des distances, etc. Je propose les techniques de dépliage suivantes, implémentées et évaluées dans des systèmes interactifs : (i) une navigation temporelle qui permet de naviguer plus efficacement entre des différents instants, ainsi qu'un feedback visuel qui permet de mieux comprendre les changements dans les réseaux entre deux instants arbitraires. (ii) Des designs permettant la comparaison directe de deux réseaux avec des liens pondérés. (iii) Un modèle de visualisation pour des réseaux denses avec des liens pondérés, ainsi que (iv) la génération de réseaux synthétiques utilisés pour l'évaluation des visualisations. Afin de mieux créer et évaluer des visualisations, nous (v) proposons une taxonomie de tâche pour décrire des tâches accomplies par des analystes des réseaux. Pour compléter, (vi) nous généralisons l'idée de dépliage pour décrire d'autres genres de données temporelles, représentable dans des cubes espace-temps. Cela concerne la visualisation de vidéos, des données multi-variées, ainsi que la géographique. Une telle généralisation a pour but de fournir une base commune pour échanger des techniques de visualisation et de mieux comprendre l'espace de design pour les réseaux dynamiques. Dans cette optique, nous proposons une taxonomie d'opérations génériques qui nous permet de transformer un cube espace-temps en visualisation bidimensionelle, ainsi qu'une description des formes évoquées par les données dans le cube espace-temps. / Networks are models that help us understanding and thinking about relationships between entities in the real world. Many of these networks are dynamic, i.e. connectivity changes over time. Understanding changes in connectivity means to understand interactions between elements of complex systems; how people create and break up friendship relations, how signals get passed in the brain, how business collaborations evolve, or how food-webs restructure after environmental changes. However, understanding static networks is already difficult, due to size, density, attributes and particular motifs; changes over time very much increase this complexity. Quantification of change is often insufficient, but beyond an analysis that is driven by technology and algorithms, humans dispose a unique capability of understanding and interpreting information in data, based on vision and cognition. This dissertation explores ways to interactively explore dynamic networks by means of visualization. I develop and evaluate techniques to unfold the complexity of dynamic networks, making them understandable by looking at them from different angles, decomposing them into their parts and relating the parts in novel ways. While most techniques for dynamic network visualization rely on one particular type of view on the data, complementary visualizations allow for higher-level exploration and analysis. Covering three aspects Tasks, Visualization Design and Evaluation, I develop and evaluate the following unfolding techniques: (i) temporal navigation between individual time steps of a network and improved animated transitions to better understand changes, (ii) designs for the comparison of weighted graphs, (iii) the Matrix Cube, a space-time cube based on adjacency matrices, allowing to visualize dense dynamic networks by, as well as GraphCuisine, a system to (iv) generate synthetic networks with the primary focus on evaluating visualizations in user studies. In order to inform the design and evaluation of visualizations, we (v) provide a task taxonomy capturing users' tasks when exploring dynamic networks. Finally, (vi) the idea of unfolding networks with Matrix Cubes is generalized to other data sets that can be represented in space-time cubes (videos, geographical data, etc.). Visualizations in these domains can inspire visualizations for dynamic networks, and vice-versa. We propose a taxonomy of operations, describing how 3D space-time cubes are decomposed into a large variety of 2D visualizations. These operations help us exploring the design space for visualizing and interactively unfolding dynamic networks and other spatio-temporal data, as well as may serve users as a mental model of the data.

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). / 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.).

Parmi les évolutions majeures de l'informatique, nous distinguons l'émergence des technologies mobiles sans fil. Le développement actuel de ces technologies permet de réaliser des communications ad-hoc directes entre de nombreux types d'entités mobiles, comme des véhicules, des robots terrestres ou des drones. Dans un réseau de tels équipements, l'ensemble des liens de communication qui existe à un instant donné dépend des distances entre les entités et la topologie du réseau change continuellement lorsque les entités se déplacent. Les hypothèses habituelles sur la connexité du réseau n'ont pas leur place ici, néanmoins, une autre forme de connexité appelée connexité temporelle est souvent disponible à travers le temps et l'espace. L'objectif de cette thèse a été de développer des algorithmes pour les flottes d'appareils dans le cas des réseaux tolérant aux délais (DTN). De manière simplifiée, les réseaux tolérants aux délais sont des réseaux pour lesquels certaines parties peuvent se retrouver isolées pendant un moment sans que cela pose problème. Nous nous intéressons, en particulier, au cas où ces appareils sont organisés sous la forme de groupes, et où la notion de groupe elle même survit à ces déconnexions transitoires. Ainsi, une grande partie de la thèse s'articule autour de la notion des groupes tolérant aux délais (groupe DTN). Dans notre cas cet éloignement est limité dans le temps et nous parlons alors de "diamètre temporel borné" au sein du groupe. Le fait de borner le diamètre temporel du groupe lui permet de distinguer entre l'éloignement temporaire d'un noeud et sa perte définitive (crash ou autre). / Among the major developments in computer science, we distinguish the emergence of mobile wireless technologies. The current development of these technologies allows for direct ad-hoc communications between many types of mobile entities, such as vehicles, land robots or drones. In a network of such devices, the set of communication links that exists at a given instant depends upon the distances between the entities. As a result, the topology of the network changes continuously as the entities move. The common assumption on connectivity may not be relevant in this case, but another kind of connectivity called temporal connectivity is often alvailable over time and space. The goal of this thesis has been the development of algorithms for fleets of mobile devices in the case of delay-tolerant networks. In a simpler way, the delay-tolerant networks are networks where some parts can be isolated during a certain time without problems. We are interested, in particular, in the case where the devices are organised as groups, and where the notion of group itself survives to these deconnections. Hence, a big part of this thesis relates to the notion of delay-tolerant groups (DTN groups). In our case, these deconnections are limited in time and we speak of a "bounded temporal diameter" within the group. The fact of limiting the temporal diameter of the group enables it to distinguish between temporary deconnections and final loss (crash or other) of some nodes.

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