ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2018, Vol. 55 ›› Issue (11): 2406-2418.doi: 10.7544/issn1000-1239.2018.20170672

Previous Articles     Next Articles

Topic-Interest Based Influence Maximization Algorithm in Social Networks

Liu Yong, Xie Shengnan, Zhong Zhiwei, Li Jinbao, Ren Qianqian   

  1. (黑龙江大学计算机科学技术学院 哈尔滨 150080) (黑龙江省数据库与并行计算重点实验室(黑龙江大学) 哈尔滨 150080) (
  • Online:2018-11-01

Abstract: Influence maximization is a problem of finding a small set of seed nodes in a social network that maximizes the spread scope of a propagation item. Existing works only take into account the topic distribution on propagation items, but ignore the interest distribution on users. This paper focuses on how to select the most influential seeds when both the topic distribution of propagation items and the interest distribution of users are taken into consideration. A topic-interest independent cascade (TI-IC) propagation model is proposed, and an expectation maximization (EM) algorithm is proposed to learn the parameters of the TI-IC model. Based on the TI-IC model, a topic-interest influence maximization (TIIM) problem is proposed, and a new heuristic algorithm called ACG-TIIM is presented to solve TIIM. ACG-TIIM first takes each user as a root node to construct a reachable path tree, roughly estimate the influence scope of each user, and then sorts all the users according to the estimated influence scope to select a small number of users as candidate seeds, finally uses the greedy algorithm with EFLF optimization to select the most influential seeds from candidate seeds. The experimental results on real datasets show that TI-IC model is superior to classical IC and TIC models in describing propagation law and predicting propagation results. ACG-TIIM can solve the TIIM problem effectively and efficiently.

Key words: social networks, influence maximization, topic distribution, propagation model, expectation maximization

CLC Number: