Multi-Community Influence Maximization in Device-to-Device social networks

摘要

In recent years, we have witnessed the rapid development of mobile multimedia services integrated with social networks. Therefore, Influence Maximization (IM) problem in social networks has become a widely studied topic, which aims to identify a small set of users (seed users) to cover as many users as possible through information propagation. Although most researches focus on online occasions or one single community, a few studies have been done for face-to-face (Device-to-Device, D2D) propagation occasions across multiple communities. General influence maximization in one community aims to find out k seed users under the given budget k, while in this paper, we concentrate on Multi-Community Influence Maximization (MCIM) problem to maximize influence (i.e., propagation coverage) by identifying seed users in multiple social communities of different properties and characteristics based on a total budget of seed users. We transform this problem into two subproblems, including Single Community Influence Maximization (SCIM) and Multi-Community Budget Allocation (MCBA). Respectively, we propose Weighted LeaderRank with Neighbors (WLRN) to rank users in a single community and design a method named Optimal Budget Allocation (OBA) to allocate budget (total quota of seed users) to multiple communities. The experiments based on a realistic D2D data set and an online social network show our method improves the propagation coverage significantly than general algorithms.