Compatible Influence Maximization in Online Social Networks

Abstract

Influence maximization, which aims to find a small number of influencers in a social network to maximize the influence spread under a certain propagation model, has attracted substantial attention due to its widespread applications, such as viral marketing and social advertising. However, most of the former studies focus primarily on maximizing the influence spread of a single product, which is not very common in actual marketing campaigns. In this article, we study a novel compatible influence maximization problem for two considered products, which involves more complex product adoption decisions of users in many realistic settings. The problem is NP-hard, and the objective function no longer exhibits monotonicity and submodularity. We propose an adapted greedy algorithm to solve the problem effectively. Due to its poor computational efficiency in the seed selection, we further propose a fast greedy algorithm that integrates several effective optimization strategies without compromising the accuracy and devise an efficient heuristic algorithm to approximate the influence spread calculation. Extensive experiments over real-world social networks of different sizes demonstrate the effectiveness and efficiency of the proposed methods.