Targeted influence maximization in competitive social networks

Advertising using the word-of-mouth effect is quite effective in promoting products. In the last decade, there has been intensive research studying the influence maximization problem in marketing. The problem of influence maximization aims to identify a small group of people in the social network as seeds such that eventually, they will trigger the largest influence spread or product adoption in the network. In practical scenarios of online marketing, it is common that there are competitions among similar products in the network and the promotion is targeted at specific groups of users. For instance, an event organizer disseminates an event ad on a social platform hoping to attract attention of the most number of local residents. Meanwhile, there are multiple competing events being promoted on the social platform. In this paper, we formulate such problem as Targeted Influence Maximization in Competitive social networks (TIMC). To model the influence diffusion, we combine the target nodes and competitive relationships into an independent cascade model. We propose a Reverse Reachable set-based Greedy (RRG) algorithm to solve the TIMC problem and theoretically proved its approximation ratio. We also design a pruning strategy to further speed up the performance of the proposed algorithm. Extensive experiments have confirmed the efficiency of the proposed RRG algorithm. We also find that the algorithm works particularly well for sparse large networks with strong competition.