Handbook of Optimization in Complex Networks Communication and Socia
This second volume of the "Handbook Optimization in Complex Networks" presents the most recent research and developments in the application of optimization techniques to the study of complex communication and social networks. This book present several opt
- PDF / 1,264,157 Bytes
- 37 Pages / 439.37 x 666.142 pts Page_size
- 89 Downloads / 204 Views
Path Formation in Human Contact Networks Nishanth Sastry and Pan Hui
Abstract The Pocket Switched Network (PSN) is a radical proposal to take advantage of short-range connectivity afforded by human face-to-face contacts, and create longer paths by having intermediate nodes ferry data on behalf of the sender. The Pocket Switched Network creates paths over time using transient social contacts. This chapter explores the achievable connectivity properties of this dynamically changing mileu, and gives a community-based heuristic to find efficient routes. We first employ empirical traces to examine the effect of the human contact process on data delivery. Contacts between a few node pairs are found to occur too frequently, leading to inadequate mixing of data, while the majority of contacts occur rarely, but are essential for global connectivity. We then examine all successful paths found by flooding and show that though delivery times vary widely, randomly sampling a small number of paths between each source and destination is sufficient to yield a delivery time distribution close to that of flooding over all paths. Thus, despite the apparent fragility implied by the reliance on rare edges, the rate at which the network can deliver data is remarkably robust to path failures. We then give a natural heuristic that finds routes by exploiting the latent social structure. Previous methods relied on building and updating routing tables to cope with dynamic network conditions. This has been shown to be cost ineffective due to the partial capture of transient network behavior. A more promising approach would be to capture the intrinsic characteristics of such networks and utilize them for
N. Sastry Kings College London, Strand, London, WC2R 2LS e-mail: [email protected] P. Hui () Deutsche Telekom Laboratories, Ernst-Reuter-Platz 7, 10587 Berlin, Germany e-mail: [email protected] M.T. Thai and P.M. Pardalos (eds.), Handbook of Optimization in Complex Networks: Communication and Social Networks, Springer Optimization and Its Applications 58, DOI 10.1007/978-1-4614-0857-4 12, © Springer Science+Business Media, LLC 2012
349
350
N. Sastry and P. Hui
routing decsions. We design and evaluate BUBBLE, a novel social-based forwarding algorithm, that utilizes the centrality and community metrics to enhance delivery performance. We empirically show that BUBBLE can efficiently identify good paths using several real mobility datasets.
12.1 Introduction Consider a scenario in which Alice wants to convey some information to Carol. If Bob happens to meet Alice first and then Carol, he could potentially serve as a messenger for Alice’s message. Essentially, this method of communication exploits human contacts to create a path over time between a source and destination. Of necessity, the data paths are constructed in a store-carry-forward fashion: Various intermediate nodes store the data on behalf of the sender and carry it to another contact opportunity where they forward the data to the destination or another node that can
Data Loading...
