On Influence Maximization to Target Users in the Presence of Multiple Acceptances

In this paper, we study a novel problem of influence maximization in social networks: Given a period of promotion time and a set of target users, each of which can be activated by its neighbors multiple times, we aim at maximizing the total acceptance frequency of these target users by initially selecting k most influential seeds. The promising viral marketing paradigm on social network is different from the current research in two main aspects. First, instead of maximizing the message spread over the entire social network, we focus on the target market since the business vendors almost specify the target users before designing its marketing strategy. Second, the status of a user is no longer a binary indicator representing either active or inactive. In the new model the user status turns to be an integer value reflecting the amount of influences delivered to that user. In this paper, we prove the NP-hard nature of this challenging problem.