During the last decade, the study of large scale complex networks has attracted a substantial amount of attention and work from several domains: sociology, biology, computer science, epidemiology. Most of such complex networks are inherently dynamic, with new vertices and links appearing while some old ones disappear. Until recently, the dynamics of these networks was less studied and there is a strong need for dynamic network models in order to sustain protocol performance evaluations and fundamental analyzes in all the research domains listed above. We propose in this paper a novel framework for the study of dynamic mobility networks. We address the characterization of dynamics by proposing an in-depth description and analysis of two real-world data sets. We show in particular that links creation and deletion processes are independent of other graph properties and that such networks exhibit a large number of possible configurations, from sparse to dense. From those observations, we propose simple yet very accurate models that allow generating random mobility graphs with similar temporal behavior as the one observed in experimental data.
19 Figures and Tables
Table 1 Graph properties: Mean and Standard Deviation of PDF, Correlation Times.
Fig. 1. Statistics of graph properties, displayed as a function of time (Imote on the left and Mit on the right).
Fig. 2. Contact (left) and Inter-contact (right) duration distributions (CCDF).
Table 2 Imote: correlation coefficients between the various graph properties.
Table 3 Number of evolution of each type for Imote (left, a) and Mit (right, b): a (+x,−y) = k cell meaning that there is k time steps where x CCs appear and y CCs disappear simultaneously.
Fig. 4. link correlation histogram for Imote (left) and Mit (right).
Table 4 Proportion of link creations that adds a new triangle or not (P ), and proportion of inactive links that, if created, would add a triangle, or not (f).
Fig. 5. Distribution of the total lifetime (left, a), number of appearances (right, b) for all CCs (+) and CCNs (x) of Imote.
Table 5 Algorithm parameters and frequent connected subgraphs properties.
Fig. 6. Joint distribution of the number of vertices and total lifetime (left, a), and joint distribution of the number of vertices and number of appearances (right, b) for all CCs of Imote.
Table 6 Proportion of links additions that creates a new triangle for the classical and weighted models.
Fig. 7. Individual trajectories in groups ordered by time. ix (boxes) are individuals while gx (circles) denotes social groups.
Fig. 8. Number of links for Imote data and model A (left), contact (middle) and Inter-contact (right) duration distributions (CCDF) for classical models and Imote.
Fig. 9. Imote: Probability distribution function for original data and the classical models.
Fig. 10. Joint distribution of the number of connected vertices and links in connected components, for the classical models (from left to right, A, B and C).
Fig. 11. Imote: Joint distribution of the number of connected vertices and links in connected components, for the weighted models (from left to right, Aω, Bω and Cω).
Fig. 12. Distribution of the total lifetime of all CCNs for C classical model (left) and C weighted model (right).
Fig. 13. Density of frequently connected components for Imote (left), classical (A, middle) and weighted models (B, right)
Fig. 14. Cω: trajectories of individuals among communities
Download Full PDF Version (Non-Commercial Use)