Online Topic-Aware Influence Maximization

Influence maximization, whose objective is to select k users (called seeds) from a social network such that the number of users influenced by the seeds (called influence spread) is maximized, has attracted significant attention due to its widespread applications, such as viral marketing and ru-mor control. However, in real-world social networks, users have their own interests (which can be represented as top-ics) and are more likely to be influenced by their friends (or friends ’ friends) with similar topics. We can increase the influence spread by taking into consideration topics. To address this problem, we study topic-aware influence maxi-mization, which, given a topic-aware influence maximization (TIM) query, finds k seeds from a social network such that the topic-aware influence spread of the k seeds is maximized. Our goal is to enable online TIM queries. Since the topic-aware influence maximization problem is NP-hard, we focus on devising efficient algorithms to achieve instant perfor-mance while keeping a high influence spread. We utilize a maximum influence arborescence (MIA) model to approx-imate the computation of influence spread. To efficiently find k seeds under the MIA model, we first propose a best-effort algorithm with 1 − 1 e approximation ratio, which esti-mates an upper bound of the topic-aware influence of each user and utilizes the bound to prune large numbers of users with small influence. We devise effective techniques to esti-mate tighter upper bounds. We then propose a faster topic-sample-based algorithm with · (1 − 1 e) approximation ratio for any ∈ (0, 1], which materializes the influence spread of some topic-distribution samples and utilizes the material-ized information to avoid computing the actual influence of users with small influences. Experimental results show that our methods significantly outperform baseline approaches. 1