Viral marketing for dedicated customers

Viral marketing has attracted considerable concerns in recent years due to its novel idea of leveraging the social network to propagate the awareness of products. Specifically, viral marketing first targets a limited number of users (seeds) in the social network by providing incentives, and these targeted users would then initiate the process of awareness spread by propagating the information to their friends via their social relationships. Extensive studies have been conducted for maximizing the awareness spread given the number of seeds (the Influence Maximization problem). However, all of them fail to consider the common scenario of viral marketing where companies hope to use as few seeds as possible yet influencing at least a certain number of users. In this paper, we propose a new problem, called J-MIN-Seed, whose objective is to minimize the number of seeds while at least J users are influenced. J-MIN-Seed, unfortunately, is NP-hard. Therefore, we develop an approximate algorithm which can provide error guarantees for J-MIN-Seed. We also observe that all existing studies on viral marketing assume that all users in the social network are of interest for the product being promoted (i.e., all users are potential consumers of the product), which, however, is not always true. Motivated by this phenomenon, we propose a new paradigm of viral marketing where the company can specify which types of users in the social network are of interest when promoting a specific product. Under this new paradigm, we re-define our J-MIN-Seed problem as well as the Influence Maximization problem and design some algorithms with provable error guarantees for the new problems. We conducted extensive experiments on real social networks which verified the effectiveness of our algorithms.