Dynamic networks like Online Social Networks or Disruption Tolerant Networks (DTNs), when considering their spatial, temporal and size complexity, even if partly wired, are exposed to nodes and links churns and failures which can be modeled with dynamic graphs with time varying edges and vertices. Recently, it has been shown that dynamic networks exhibit some regularity in their temporal contact patterns. The impact of this regularity on network performances has not been well studied and analyzed. One of the most interesting problem in research on dynamic networks is the issue of efficient navigation techniques in such networks. For dynamic networks, because there is still no widely developed theoretical background to understand deeply the problems, research traditionally tends to propose heuristic solutions. In the context of DTNs, these solutions tend to answer to some specific questions about navigating in a dynamic network (e.g., how to reduce energy consumption of routing, how to maximize the delivery probability) while usually ignoring and not leveraging on the profound structural properties of the dynamic network. In this work, we aim to contribute to understanding the impact of this dynamic structure on information routing and show how to exploit this structure for efficient navigation in such networks.

The small-world phenomenon first introduced in the context of static graphs consists of graphs with high clustering coefficient and low shortest path length. This is an intrinsic property of many real complex static networks. Recent research has shown that this structure is also observable in dynamic networks but how it emerges remains an open problem. In this paper, we propose a model capable of capturing the small-world behavior observed in various real traces. We then study information diffusion in such small-world networks. Analytical and simulation results with epidemic model show that the small-world structure increases dramatically the information spreading speed in dynamic networks.

This paper introduces a Swarm-Intelligence based Routing protocol (SIR) that aims to efficiently route information in content centric Delay Tolerant Networks (CCDTN) also dubbed pocket switched networks. First, this paper formalizes the notion of optimal path in CCDTN and introduces an original and efficient algorithm to process these paths in dynamic graphs. The properties and some invariant features of these optimal paths are analyzed and derived from several real traces. Then, this paper shows how optimal path in CCDTN can be found and used from a fully distributed swarm-intelligence based approach of which the global intelligent behavior (i.e. shortest path discovery and use) emerges from simple peer to peer interactions applied during opportunistic contacts. This leads to the definition of the SIR routing protocol of which the consistency, efficiency and performances are demonstrated from intensive representative simulations.