Profit maximization for viral marketing in Online Social Networks

Information can be disseminated widely and rapidly through Online Social Networks (OSNs) with 'word-of-mouth' effects. Viral marketing is such a typical application in which new products or commercial activities are advertised by some seed users in OSNs to other users in a cascading manner. The budget allocation for seed selection reflects a tradeoff between the expense and reward of viral marketing. In this paper, we define a general profit metric that naturally combines the benefit of influence spread with the cost of seed selection in viral marketing to eliminate the need for presetting the budget for seed selection. We carry out a comprehensive study on finding a set of seed nodes to maximize the profit of viral marketing. We show that the profit metric is significantly different from the influence metric in that it is no longer monotone. As a result, from the computability perspective, the problem of profit maximization is much more challenging than that of influence maximization. We develop new seed selection algorithms for profit maximization with strong approximation guarantees. Experimental evaluations with real OSN datasets demonstrate the effectiveness of our algorithms.