Exploring social structures for network protocol designs

Abstract

With the proliferation of wireless mobile devices, such as smartphone and tablet, social networks have been evolving to link humans, mobile devices and technological networks together. Human behaviors have been more closely connected with the technological networks than ever before, such as Delay Tolerant Networks (DTN), Online Social Networks (OSN) and mobile social networks. Due to the involvement of the humans, social structures of humans provide the crucial information of network structure and node organization, and thus can be exploited for network protocol designs in these networks. Overall, this thesis focuses on two major issues: how to identify the social structures in network and how to exploit these social structures for network protocol designs. The detection of community is an important issue due to its wide use in network protocol designs and most of current community detection algorithms only focus on binary networks. However, most networks are weighted such as social networks, DTN or OSN. To simplify the analysis or design, these networks are formulated as binary networks. However, some important information of a weighted network is lost, and hence weakens the network performance. To this end, we address the problems of community detection in weighted networks and exploit community to design data forwarding in DTN and worm containment in OSN. Mobile social network plays a fundamental role as a medium for information diffusion and it has been utilized as a platform for viral marketing through the power of ``word-of-mouth''. As the essence of viral marketing applications is the information diffusion from a small number of individuals to the network by ``word-of-mouth'', we address the problem of identifying a small number of individuals through whom the information can be diffused to the network as soon as possible, referred as diffusion minimization problem. Unfortunately, the diffusion minimization problem under probabilistic diffusion model is NP-hard and log n-hard to approximate. We investigate how to solve this hard problem by employing the community structure. To tackle the problem that community structure might not be accurate when applied for node contact prediction and might separate two frequent connected nodes into different communities, we introduce a novel social structure--skeleton, which is constructed based on the best friend relations. We address the challenges on how to uncover skeleton from network, how to handle the dynamic evolving of skeleton and how to design network protocols based on skeleton. By investigating social structure for network protocol design, we can conclude that, for the networks involved with human activities, social structure is a salient property to better facilitate the design of network protocols.