Social Network Analysis of Human Mobility and Implications for DTN Performance Analysis and Mobility Modeling

Abstract

Social Network Analysis (SNA) has emerged as a promising method for designing data dissemination algorithms over Delay Tolerant Networks (DTN). These algorithms try to identify and exploit macroscopic regular relationships between nodes. Despite initial encouraging results, the type and complexity of the alleged underlying social structure has not been sufficiently studied or quantified. In this paper, we perform a systematic study and comparison of 4 mobility traces and 3 state-of-the-art synthetic models with respect to social properties. We represent each model as a weighted contact graph and study community structure, graph spectrum, inter- and intra-community weight distributions, etc. We also discuss the implications for synthetic mobility models. Finally, to underline the importance of these contact graph properties, we (i) show that the delay of distributed estimation depends on the second largest eigenvalue of the nor malized weighted contact graph, and (ii) express the performance of various (random and SNA-based) DTN routing schemes as a function of the volume of cuts between communities.