Skeleton construction in mobile social networks: Algorithms and applications

Mobile social networks have emerged as a new frontier in the mobile computing research society, and the commonly used social structure (i.e., community) has been exploited to facilitate the design of network protocols and applications, such as data forwarding and worm containment. However, community based approaches may not be accurate when applied for predicting node contacts and may separate two frequently contacted nodes into different communities. In this paper, to address these problems, we propose skeleton, a tree structure specially designed for organizing network nodes, as the underlying structure in mobile social networks. We address the challenges on how to uncover skeleton from network, how to adapt skeleton with dynamic network and how to leverage skeleton for network protocol designs. Skeleton is constructed based on best friendship and skeleton construction is simple and efficient (e.g., less computational complexity than community detection). Algorithms are also designed to adapt skeleton construction to dynamic network. Moreover, a data forwarding algorithm and a worm containment strategy are designed based on skeleton. Trace-driven simulation results show that the skeleton based data forwarding algorithm and worm containment strategy outperform existing schemes based on community.