Portal de Periódicos da CAPES

Positive influence maximization in signed social networks based on simulated annealing

2017; Elsevier BV; Volume: 260; Linguagem: Inglês

10.1016/j.neucom.2017.03.003

1872-8286

Dong Li, Cuihua Wang, Shengping Zhang, Guanglu Zhou, Dianhui Chu, Chong Wu,

Social Media and Politics

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.