Section: Overall Objectives

Highlights of the Year

Model for Time-Varying Graphs.

We propose a novel model for representing finite discrete Time-Varying Graphs (TVGs). The major application of such a model is for the modelling and representation of dynamic networks. In our proposed model, an edge is able to connect a node $u$ at a given time instant $t_a$ to any other node $v$ ($u$ possibly equal to $v$) at any other time instant $t_b$ ($t_a$ possibly equal to $t_b$), leading to the concept that such an edge can be represented by an ordered quadruple of the form $(u,t_a,v,t_b)$. Building upon this basic concept, our proposed model defines a TVG as an object $H=(V,E,T)$, where $V$ is the set of nodes, $E\subseteq V\times T\times V\times T$ is the set of edges, and $T$ is the finite set of time instants on which the TVG is defined. We show how key concepts, such as degree, path, and connectivity, are handled in our model. We also analyse the data structures used for the representation of dynamic networks built following our proposed model and demonstrate that, for most practical cases, the asymptotic memory complexity of our TVG representation model is determined by the cardinality of the set of edges. (See [20] )

Tight bounds on the contiguity and linearity of co-graphs.

We show that the contiguity and linearity of co-graphs on n vertices are both O(log n). Moreover, we show that this bound is tight for contiguity as there exists a family of cographs on n vertices whose contiguity is Omega(log n). We also provide an Omega(log n / log log n) lower bound on the maximum linearity of co-graphs on n vertices. As a by-product of our proofs, we obtain a min-max theorem, which is worth of interest in itself, stating equality between the rank of a tree and the minimum height of one of its path partitions. (See [3] )

Function analysis through wavelets on dynamic contact graphs.

Parameters of the diffusion and of the mutations of nosocomial bacteria strains are still today not completely understood. The macroscopic mechanisms involved during the diffusion are opposed to microscopic mechanisms which are well known and understood. At the scale of an hospital, this is a complex system that needs to be be simplified and modelled before an epidemiological study of the whole system. We aim at giving an answer to the question of whether there exists a correlation between the contact graph (dynamic network) and the microbiological diffusion of the strains of Staphylococcus Aureus bacteria. For that purpose, the research project MOSAR (Mastering hOSpital Antimicrobial Resistance) and the i-Bird group (Individual Based Investigation of Resistance Dissemination) designed a large scale experiment that has been carried out at the Hospital of Berck-sur-Mer (FRANCE). Our work focuses on comparing the diffusion of some selected strains to the results obtained with wavelets on the aggregated contact graph, the selection being made such as the strains show a clear diffusion over time. We study the correlation between the spatial diffusion of the wavelets and the spatio-temporal diffusion of those strains.

Hierarchical Modelling of IEEE 802.11 Multi-hop Wireless Networks.

IEEE 802.11 is implemented in many wireless networks, including multi-hop networks where communications between nodes are conveyed along a chain. We present a modelling framework to evaluate the performance of flows conveyed through such a chain. Our framework is based on a hierarchical modelling composed of two levels. The lower level is dedicated to the modelling of each node, while the upper level matches the actual topology of the chain. Our approach can handle different topologies, takes into account Bit Error Rate and can be applied to multi-hop flows with rates ranging from light to heavy workloads. We assess the ability of our model to evaluate loss rate, throughput, and end-to-end delay experienced by flows on a simple scenario, where the number of nodes is limited to three. Numerical results show that our model accurately approximates the performance of flows with a relative error typically less than 10%.

Awards and honours

Hurst Exponent IntraPartum Fetal Heart Rate: Impact of Decelerations [7] was granted the best paper award in the 26th IEEE International Symposium on Computer-Based Medical Systems (CBMS).

Best Paper Award :

[7] Hurst Exponent IntraPartum Fetal Heart Rate: Impact of Decelerations in IEEE 26th International Symposium on Computer-Based Medical Systems (CBMS), 2013.

P. Abry, S. Roux, V. Chudáček, P. Borgnat, P. Gonçalves, M. Doret.