Influence Maximization in Signed Social Networks

Influence Maximization is the problem of choosing a small set of seed users within a larger social network in order to maximize the spread of influence under certain diffusion models. The problem has been widely studied and several solutions have been proposed. Previous work has concentrated on positive relationships between users, with little attention given to the effect of negative relationships of users and the corresponding spread of negative opinion. In this paper we study influence maximization in signed social networks and propose a new diffusion model called LT-S, which is an extension to the classical linear threshold model incorporating both positive and negative opinions. To the best of our knowledge, we are the first to study the influence maximization problem in signed social networks with opinion formation. We prove that the influence spread function under the LT-S model is neither monotone nor submodular and propose an improved R-Greedy algorithm called RLP. Extensive experiments conducted on real signed social network datasets demonstrate that our algorithm outperforms the baseline algorithms in terms of efficiency and effectiveness.