Positive influence maximization in signed social networks based on simulated annealing

Current studies of influence maximization focus almost exclusively on unsigned social networks ignoring the polarities of the relationships between users. Influence maximization in signed social networks containing both positive relationships (e.g., friend or like) and negative relationships (e.g., enemy or dislike) is still a challenging problem which remains much open. A few studies made use of greedy algorithms to solve the problem of positive influence or negative influence maximization in signed social networks. Although greedy algorithm is able to achieve a good approximation, it is computational expensive and not efficient enough. Aiming at this drawback, we propose an alternative method based on Simulated Annealing (SA) for the positive influence maximization problem in this paper. Additionally, we also propose two heuristics to speed up the convergence process of the proposed method. Comprehensive experiments results on three signed social network datasets, Epinions, Slashdot and Wikipedia, demonstrate that our method can yield similar or better performance than the greedy algorithms in terms of positive influence spread but run faster.