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