Discount Allocation for Benefit Maximization in Social Networks

Social networks are becoming important dissemination platforms and a large body of works have been performed on viral marketing, but most works study the benefit associated with the number of active nodes. In this paper, we study the benefit related to interactions among activated nodes. Furthermore, a real advertising campaign is often conducted with discount instead of free sample, since discount has been demonstrated to be an effective method to promote the customers’ purchase behavior. Motivated by the above observations, we propose a new problem named discount allocation for benefit maximization, where a few selected users are offered with discounts and hope that they promote this influence to their friends so as to maximize the benefit between all influenced users. We analyze its complexity and propose a new method which decomposes the non-submodular objective function into the difference of two submodular functions and design three algorithms which are guaranteed to monotonically increase the objective function at every step.