Maintaining social connections through direct link placement in wireless networks

Mobile Social Network (MSN), built on inter-connected mobile devices, enables the flexibility of information exchanges of individuals within a virtual community. MSN may be self-organized and/or infrastructure-less, and the communication links may frequently fluctuate. When link qualities degrade, it remains critical to maintain the connections of important social pairs when supporting all social pairs is impossible. To achieve this goal, we propose to proactively place some reliable links (e.g., satellite links or UAV links) into the underlying communication network, so as to improve the service quality of the important social pairs, referred to as the Maintaining Social Connections (MSC) problem. We formulate the MSC problem and prove it is NP-hard. As such, we first study a special case of MSC, which is submodular and solvable with high approximation-ratio. Since the general MSC problem is not submodular, we propose an efficient approximation algorithm. Specially, by carefully choosing two submodular functions to lower/upper bound the MSC problem, we are able to prove the high approximation ratio of the proposed algorithm using these selected submodular functions. We further develop evolutionary algorithms to iteratively adjust the link placement via different exploration strategies, which also yield guaranteed approximation-ratio. Extensive evaluations based on both synthetic and real-world social network traces demonstrate the effectiveness of our proposed algorithms.