Antibiotic-resistance of hospital-acquired infections is a major public health issue. The worldwide emergence and diffusion of extended-spectrum β-lactamase (ESBL)-producing Enterobacteriaceae, including Escherichia coli (ESBL-EC) and Klebsiella pneumoniae (ESBL-KP), is of particular concern. Preventing their nosocomial spread requires understanding their transmission. Using Close Proximity Interactions (CPIs), measured by wearable sensors, and weekly ESBL-EC-and ESBL-KP-carriage data, we traced their possible transmission paths among 329 patients in a 200-bed long-term care facility over 4 months. Based on phenotypically defined resistance profiles to 12 antibiotics only, new bacterial acquisitions were tracked. Extending a previously proposed statistical method, the CPI network's ability to support observed incident-colonization episodes of ESBL-EC and ESBL-KP was tested. Finally, mathematical modeling based on our findings assessed the effect of several infection-control measures. A potential infector was identified in the CPI network for 80% (16/20) of ESBL-KP acquisition episodes. The lengths of CPI paths between ESBL-KP incident cases and their potential infectors were shorter than predicted by chance (P = 0.02), indicating that CPI-network relationships were consistent with dissemination. Potential ESBL-EC infectors were identified for 54% (19/35) of the acquisitions, with longer-than-expected lengths of CPI paths. These contrasting results yielded differing impacts of infection control scenarios, with contact reduction interventions proving less effective for ESBL-EC than for ESBL-KP. These results highlight the widely variable transmission patterns among ESBL-producing Enterobacteriaceae species. CPI networks supported ESBL-KP, but not ESBL-EC spread. These outcomes could help design more specific surveillance and control strategies to prevent in-hospital Enterobacteriaceae dissemination.

The interaction among multiple microbial strains affects the spread of infectious diseases and the efficacy of interventions. Genomic tools have made it increasingly easy to observe pathogenic strains diversity, but the best interpretation of such diversity has remained difficult because of relationships with host and environmental factors. Here, we focus on host-to-host contact behavior and study how it changes populations of pathogens in a minimal model of multi-strain interaction. We simulated a population of identical strains competing by mutual exclusion and spreading on a dynamical network of hosts according to a stochastic susceptible-infectious-susceptible model. We computed ecological indicators of diversity and dominance in strain populations for a collection of networks illustrating various properties found in real-world examples. Heterogeneities in the number of contacts among hosts were found to reduce diversity and increase dominance by making the repartition of strains among infected hosts more uneven, while strong community structure among hosts increased strain diversity. We found that the introduction of strains associated with hosts entering and leaving the system led to the highest pathogenic richness at intermediate turnover levels. These results were finally illustrated using the spread of Staphylococcus aureus in a long-term health-care facility where close proximity interactions and strain carriage were collected simultaneously. We found that network structural and temporal properties could account for a large part of the variability observed in strain diversity. These results show how stochasticity and network structure affect the population ecology of pathogens and warn against interpreting observations as unambiguous evidence of epidemiological differences between strains.

Our usage of language is not solely reliant on cognition but is arguably determined by myriad external factors leading to a global variability of linguistic patterns. This issue, which lies at the core of sociolinguistics and is backed by many small-scale studies on face-to-face communication, is addressed here by constructing a dataset combining the largest French Twitter corpus to date with detailed socioeconomic maps obtained from national census in France. We show how key linguistic variables measured in individual Twitter streams depend on factors like socioeconomic status, location, time, and the social network of individuals. We found that (i) people of higher socioeconomic status, active to a greater degree during the daytime, use a more standard language; (ii) the southern part of the country is more prone to use more standard language than the northern one, while locally the used variety or dialect is determined by the spatial distribution of socioeconomic status; and (iii) individuals connected in the social network are closer linguistically than disconnected ones, even after the effects of status homophily have been removed. Our results inform sociolinguistic theory and may inspire novel learning methods for the inference of socioeconomic status of people from the way they tweet.

The GraSP toolbox aims at processing and visualizing graphs and graphs signal with ease. In the demo, we show those capabilities using several examples from the literature and from our own experiments.

We analyze a coupled dataset collecting the mobile phone communication and bank transactions history of a large number of individuals living in Mexico. After mapping the social structure and introducing indicators of socioeconomic status, demographic features, and purchasing habits of individuals we show that typical consumption patterns are strongly correlated with identified socioeconomic classes leading to patterns of stratification in the social structure. In addition we measure correlations between merchant categories and introduce a correlation network, which emerges with a meaningful community structure. We detect multivariate relations between merchant categories and show correlations in purchasing habits of individuals. Our work provides novel and detailed insight into the relations between social and consuming behaviour with potential applications in recommendation system design.

Many dynamic networks coming from real-world contexts are link streams, i.e. a finite collection of triplets (u,v,t) where u and v are two nodes having a link between them at time t. A great number of studies on these objects start by aggregating the data on disjoint time windows of length Δ in order to obtain a series of graphs on which are made all subsequent analyses. Here we are concerned with the impact of the chosen Δ on the obtained graph series. We address the fundamental question of knowing whether a series of graphs formed using a given Δ faithfully describes the original link stream. We answer the question by showing that such dynamic networks exhibit a threshold for Δ, which we call the saturation scale, beyond which the properties of propagation of the link stream are altered, while they are mostly preserved before. We design an automatic method to determine the saturation scale of any link stream, which we apply and validate on several real-world datasets.

Graph-based models form a fundamental aspect of data representation in Data Sciences and play a key role in modeling complex networked systems. In particular, recently there is an ever-increasing interest in modeling dynamic complex networks, i.e. networks in which the topological structure (nodes and edges) may vary over time. In this context, we propose a novel model for representing finite discrete Time-Varying Graphs (TVGs), which are typically used to model dynamic complex networked systems. We analyze the data structures built from our proposed model and demonstrate that, for most practical cases, the asymptotic memory complexity of our model is in the order of the cardinality of the set of edges. Further, we show that our proposal is an unifying model that can represent several previous (classes of) models for dynamic networks found in the recent literature, which in general are unable to represent each other. In contrast to previous models, our proposal is also able to intrinsically model cyclic (i.e. periodic) behavior in dynamic networks. These representation capabilities attest the expressive power of our proposed unifying model for TVGs. We thus believe our unifying model for TVGs is a step forward in the theoretical foundations for data analysis of complex networked systems.

Close proximity interactions (CPIs) measured by wireless electronic devices are increasingly used in epidemiological models. However, no evidence supports that electronically collected CPIs inform on the contacts leading to transmission. Here, we analyzed Staphylococcus aureus carriage and CPIs recorded simultaneously in a long-term care facility for 4 months in 329 patients and 261 healthcare workers to test this hypothesis. In the broad diversity of isolated S. aureus strains, 173 transmission events were observed between participants. The joint analysis of carriage and CPIs showed that CPI paths linking incident cases to other individuals carrying the same strain (i.e. possible infectors) had fewer intermediaries than predicted by chance (P < 0.001), a feature that simulations showed to be the signature of transmission along CPIs. Additional analyses revealed a higher dissemination risk between patients via healthcare workers than via other patients. In conclusion, S. aureus transmission was consistent with contacts defined by electronically collected CPIs, illustrating their potential as a tool to control hospital-acquired infections and help direct surveillance.

In this letter, we propose a new shift operator for graph signals, enforcing that our operator is isometric. Doing so, we ensure that as many properties of the time shift as possible get carried over. Finally, we show that our operator behaves reasonably for graph signals.

In this contribution, we investigate a graph to signal mapping with the objective of analysing intricate structural properties of graphs with tools borrowed from signal processing. We successfully use a graph-based semi-supervised learning approach to map nodes of a graph to signal amplitudes such that the resulting time series is smooth and the procedure efficient and scalable. Theoretical analysis of this method reveals that it essentially amounts to a linear graph-shift-invariant filter with the a priori knowledge put into the training set as input. Further analysis shows that we can interpret this filter as a Wiener filter on graphs. We finally build upon this interpretation to improve our results.

Using a large database (∼215,000 records) of relevant articles, we empirically study the complex systems field and its claims to find universal principles applying to systems in general. The study of references shared by the articles allows us to obtain a global point of view on the structure of this highly interdisciplinary field. We show that its overall coherence does not arise from a universal theory, but instead from computational techniques and fruitful adaptations of the idea of self‐organization to specific systems. We also find that communication between different disciplines goes through specific “trading zones,” i.e., subcommunities that create an interface around specific tools (a DNA microchip) or concepts (a network).

In order to find a cover which allows nodes to be shared among several communities, we propose a simple fuzzy community detection algorithm, which is based on an existing partition detection technique. For the performance of overlapping nodes that makes the partition ambiguous, a new extended modularity is introduced to qualify covers. With modularity optimization, the cover can be found with a high quality. We applied our method to real networks. The results demonstrate that our method can discover meaningful fuzzy community structure, overlapping community structure and hierarchical structure.

This paper presents a description of SensLAB(Very Large Scale Open Wireless Sensor Network Testbed) that has been developed and deployed in order to allow the evaluation through experimentations of scalable wireless sensor network protocols and applications. SensLAB’s main and most important goal is to offer an accurate open access multi-users scientific tool to support the design, the development tuning, and the experimentation of real large-scale sensor network applications. The SensLAB testbed is composed of 1024 nodes over 4 sites. Each site hosts 256 sensor nodes with specific characteristics in order to offer a wide spectrum of possibilities and heterogeneity. Within a given site, each one of the 256 nodes is able both to communicate via its radio interface to its neighbors and to be configured as a sink node to exchange data with any other ” sink node ”. The hardware and software architectures that allow to reserve, configure, deploy firmwares and gather experimental data and monitoring information are described. We also present demonstration examples to illustrate the use of the SensLAB testbed and encourage researchers to test and benchmark their applications/protocols on a large scale WSN testbed.

In this paper, we present for mobile ad hoc networks an efficient distributed address allocation protocol which is immune to topology changes caused by node's mobility. Contrary to the common belief that mobility makes protocol design more difficult, we show that node's mobility can, in fact, be useful to provide efficient address allocation in ad hoc networks. In our protocol, each node that has been assigned an address manages a disjoint subset of free addresses independently. By taking advantage of node mobility, we can achieve roughly even distribution of free addresses amongst nodes in the system, which enables a new joining node to be configured by its neighbors via only local communication. Theoretical analysis and extensive simulation results are presented. We show that most of the address allocation requests can be processed in a timely fashion via local communication in the requester's neighborhood with time and message complexity in the order of node's degree, regardless of the network size.

In Delay Tolerant Networks (DTN), diffusion protocols can benefit from the users' mobility in order to reach some distant nodes. However, existing protocols like flooding present a rather high overhead because of redundant transmissions. The main contribution of this paper is to introduce a new diffusion protocol, called CBD (Clustering Based data Diffusion). Our solution provides to each node the possibility to adapt its diffusion strategy on-the-fly for a more efficient diffusion by evaluating its local density. We show through the use of a real measurements mobility that CBD brings an improvement in forwarding performances, in terms of delivery ratio, delay and the amount of generated messages.

We aim to save energy by scheduling periodic sensors' duty cycles. Different from existing works, we integrate two important tasks, collision avoidance and duty cycling, into one scheduling of sensors' activities. Our scheme consists of two parts: acoloring schemethat assigns a "color" to each sensor and acolor scheduling schemethat associates each color with a schedule. Each sensor switches between sleep and active modes according to the schedule associated with its color. We propose a coloring definition. Theoretical analyses and simulation results show that, if this coloring is used by collision avoidance schemes such as TDMA or CDMA, connectivity can be guaranteed by using much less colors than traditional colorings. Theoretical analyses and simulation evaluations are presented for our scheduling. As compared to handling collision avoidance and duty cycling separately, performances can be improved by integrating these two tasks into one carefully designed schedule of sensors' activities. In particular, in duty cycled dense networks, in order to reduce packet latency and save energy, it is desirable to guarantee the communication connectivity of links only in a sparse connected subgraph.

Our goal is to save energy in wireless sensor networks (WSNs) by periodic duty-cycling of sensor nodes. We schedule sensor nodes between active (transmit or receive) and sleep modes while bounding packet latency in the presence of collisions. In order to support a dynamic WSN topology, we focus on topology-transparent approaches to scheduling; these are independent of detailed topology information. Much work has been done on topology-transparent scheduling in which all nodes are active. In this work, we examine the connection between topology-transparent duty-cycling and such non-sleeping schedules. This suggests a way to construct topology-transparent duty-cycling schedules. We analyse the performance of topology-transparent schedules with a focus on throughput in the worst case. A construction of topology-transparent duty-cycling schedules based on a topology-transparent non-sleeping schedule is proposed. The constructed schedule achieves the maximum average throughput in the worst case if the given non-sleeping schedule satisfies certain properties.

We present Worldsens,a prototyping and development work for wireless sensor protocols and applications.Our relies on two simulators,WSim and WSNet, and proposes a full simulation and performance estimation embedded platforms with instruction and radio byte curacy.During this demo,we propose to demonstrate the interest of the two simulators in stand-alone and in cooperative use.

In this paper we present Worldsens, an integrated environment for development and rapid prototyping of wireless sensor network applications. Our environment relies on software simulation to help the designer during the whole development process. The refinement is done starting from the high level design choices down to the target code implementation, debug and performance analysis. In the early stages of the design, high level parameters, like for example the node sleep and activity periods, can be tuned using WS-Net, an event driven wireless network simulator. WSNet uses models for applications, protocols and radio medium communication with a parameterized accuracy. The second step of the sensor network application design takes place after the hardware implementation choices. This second step relies on the WSim cycle accurate hardware platform simulator. WSim is used to debug the application using the real target binary code. Precise performance evaluation, including real-time analysis at the interrupt level, are made possible at this low simulation level. WSim can be connected to WSNet, in place of the application and protocol models used during the high level simulation to achieve a full distributed application simulation. WSNet and WSNet+WSim allow a continuous refinement from high level estimations down to low level real-time validation. We illustrate the complete application design process using a real life demonstrator that implements a hello protocol for dynamic neighborhood discovery in a wireless sensor network environment.

In wireless sensor networks, hello protocols for neighbor discovery are a basic service offered by the networking stack. However, their study usually rely on rather simplistic models. In this paper we study the impact of radio interferences on neighbor discovery and we introduce an analytical model to estimate the average number of neighbors that a node may expect to discover in his neighborhood.

This paper outlines the concept of auto-organization in IPv6 networks. If the auto-configuration of hosts is defined by IPv6 and mandatory, these mechanisms can not be assimilated to a fully plug and play feature as IPv6 routers still have to be manually configured. In order to succeed in new domains such as SOHO, a full auto-configuration feature must be offered. Indeed, the configuration of 64 bits IPv6 prefixes and the numbering of links are not really friendly and are error prone especially in home networking. This paper tackles the issues that arise, reviews actual solutions and proposes a totally distributed protocol named NAP for IPv6 routers auto-configuration.

Network measurement is essential for assessing performance issues, identifying and locating problems. Two common strategies are the passive approach that attaches specific devices to links in order to monitor the traffic that passes through the network and the active approach that generates explicit control packets in the network for measurements. One of the key issues in this domain is to minimize the overhead in terms of hardware, software, maintenance cost and additional traffic.In this paper, we study the problem of assigning tap devices for passive monitoring and beacons for active monitoring. Minimizing the number of devices and finding optimal strategic locations is a key issue, mandatory for deploying scalable monitoring platforms. In this article, we present a combinatorial view of the problem from which we derive complexity and approximability results, as well as efficient and versatile Mixed Integer Programming (MIP) formulations.

The dense multicast zone routing protocol (DMZ) presents a novel approach for robust multicast in mobile ad hoc networks by providing adaptive mesh oriented structures. This paper introduces the notion of dense zone, a high concentration of multicast members in a certain area of the network. Each dense zone owns leader(s) that connect to the multicast source. These leader(s) are the node members located on the upper frontier and thus nearest to the multicast source. This concept provides more robustness and scalability for multicast data transmission in ad hoc networks.

To deploy a protocol in a network, a deep performance study has to be carried out. In particular, in the case of ad hoc networks, this performance is principally tied to overhead optimization. In fact, bandwidth limitation and frequent collisions in ad hoc networks represent constraints upon deploying applications which overhead is important. In this paper, we are interested in minimizing overhead due to the deployment of an application we think is relevant to be deployed in ad hoc networks. This application, called service location, aims to make it possible for a mobile user to know about provided services in the network. In this context, we propose an analysis to estimate consumed overhead in different service location approaches. Our analysis is motivated by network and ad hoc application modeling and estimation of overhead due to service covering and request handling.

Distributed computing applications rely on transmissions of messages between processes. However, as workstations are not intended to manage this kind of communications, it is necessary to use some communication tools known as message passing libraries. Currently, MPI (Message Passing Interface) and PVM (Parallel Virtual Machine) are the most used. In addition, the need for interoperability among the rapidly proliferating amount of hardware and software led to the definition of CORBA (Common Object Request Broker Architecture), which standardizes the execution support of distributed object applications. This architecture offers good interoperability and encapsulation support. Moreover, its method invocation mechanism, offers several features and can be used as a good communication model. Consequently, the use of such an architecture for distributed and grid computing applications seems interesting and promising. However, CORBA is always criticized on the performance level. By taking account of all these elements, a performance evaluation of CORBA seems necessary. The aim of the paper is to present benchmark results of some CORBA implementations (ORBacus and TAO) and to compare them with those of the two message passing libraries MPI (MPICH and LAM) and PVM, by using a Network of WorkStations (NOW).

With the increasing number of Internet services, extensive research on service location protocols is an essential feature for future networks. In this paper, we discuss a service location and declaration protocol in ad hoc wireless environments. Our on demand protocol is based on a distributed approach which contributes to overhead optimization. The main features of our protocol are: overhead minimization, minimizing the time spent to respond to a client request, increasing the probability a client is served by the nearer service and its independence from the underlying protocols.

A core-based forwarding multicast protocol uses a core router as a traffic transit center: All multicast packets are first sent to the core, then distributed to destinations on a multicast tree rooted at the core. The purpose of this paper was to evaluate, via simulation, the effect of various core selection methods on multicast performance. Performance metrics of interest include network resource usage, packet delay, the join time of multicast participants, and link congestion. In addition, we assess the feasibility of these heuristics in real-world environments. The main contribution of this work is the discovery of a simple yet effective core selection heuristic that can be implemented in a wide variety of networks. Specifically, our results show that the tree center heuristic (using the center of the existing multicast tree as the new core node) significantly outperforms heuristics based on random selection and performs as well as other heuristics that are computationally more expensive. © 2000 John Wiley & Sons, Inc.

We propose solutions to several multicast core management problems, including automatic core selection, core failure handling, and core migration, for use in networks based on link-state routing. The proposed approach uses a central server, called the core binding server (CBS), to manage core-group bindings, accompanied by a network-level leader election protocol in order to achieve robustness. By modeling the selection of the CBS as a leader election problem, this approach can handle any combination of network component failures, including those that partition the network. Further, our simulation results reveal that the central server can sustain extremely high workloads, and demonstrate the effectiveness of our core selection and core migration methods.

A core-based forwarding multicast protocol uses a core router as a traffic transit center: all multicast packets are first sent to the core, then distributed to destinations on a multicast tree rooted at the core. The purpose of this paper is to evaluate, via simulation, the effect of various core selection methods on multicast performance. The main contribution of this work is the discovery of a simple yet effective core selection heuristic that can be implemented in a wide range of networks. Specifically, our results show that the tree center heuristic (using the center of the existing multicast tree as the new core node) significantly outperforms heuristics based on random selection, and performs as well as heuristics that are more computationally expensive.

Most machines of the last generation of distributed memory parallel computers possess specific routers which are used to exchange messages between nonneighboring nodes in the network. Among the several technologies, wormhole routing is usually preferred because it allows low channel-setup time and reduces the dependency between latency and internode distance. However, wormhole routing is very susceptible to deadlock because messages are allowed to hold many resources while requesting others. Therefore, designing deadlock-free routing algorithms using few hardware facilities is a major problem for wormhole-routed networks. In this paper, we describe a general theoretical framework for the study of deadlock-free routing functions. We give a general definition of what can be a routing function. This definition captures many specific definitions of the literature (e.g., vertex dependent, input-dependent, source-dependent, path-dependent etc.). Using our definition, we give a necessary and sufficient condition which characterizes deadlock-free routing functions. Our theory embraces, at a high level, most of the theories related to deadlock avoidance in wormhole-routed networks previously derived in the literature. In particular, it applies not only to one-to-one routing, but also to one-to-many routing. The latter paradigm is used to solve the multicast problem with the path-based or tree-based facility.

This article presents new multicasting algorithms for the mesh under the wormhole routing mode and using the read-and-route facility. These new algorithms perform generally faster than the algorithms previously described in the literature under the same model. We take, as criteria to compare the algorithms, the off-line computation time necessary to prepare the multicast, and the communication time to complete the multicast in absence of traffic. Moreover, since it is often not possible to derive useful expression for the communication time, we also simulate the algorithms.