Location And Topic-aware Influence Maximization

Although influence maximization,which selects a set of users in a social network to maximize the expected number of users influenced by the selected users(called influence spread),has been extensively studied,existing works neglected the fact that other factors can play an important role in influence maximization,such as user location and interest/preference(which can be represented as topics).Many real-world applications such as location-aware word-of-mouth marketing have location-aware requirement.Also,in real-world social networks,users have their own interests(which can be represented as topics)and are more likely to be influenced by their friends(or friends' friends)with similar topics.To meet these two requirements,we study the location-aware influence maximization and topic-aware influence maximization problem.To address location-aware challenge,we propose two greedy algorithms with 1-1/e approximation ratio.To meet the instant-speed requirement,we propose two efficient algorithms with ? ·(1-1/e)approximation ratio for any ? ?(0,1].To address the topicaware influence maximization problem,we first propose a best-effort algorithm with 1-1/e approximation ratio,which estimates 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 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 materialized information to avoid computing the actual influence of users with small influences.Experimental results on real datasets show our method achieves high performance while keeping large influence spread and significantly outperforms state-of-the-art algorithms.