Profit Maximization Under Group Influence Model in Social Networks

People with the same interests, hobbies or political orientation always form a group to share all kinds of topics in Online Social Networks (OSN). Product producers often hire the OSN provider to propagate their advertisements in order to influence all possible potential groups. In this paper, a group is assumed to be activated if beta percent of members are activated. Product producers will gain revenue from all activated groups through group-buying behavior. Meanwhile, to propagate influence, producers need pay diffusion cost to the OSN provider, while the cost is usually relevant to total hits on the advertisements. We aim to select k seed users to maximize the expected profit that combines the benefit of activated groups with the diffusion cost of influence propagation, which is called Group Profit Maximization (GPM) problem. The information diffusion model is based on Independent Cascade (IC), and we prove GPM is NP-hard and the objective function is neither submodular nor supermodular. We develop an upper bound and a lower bound that both are difference of two submodular functions. Then we design an Submodular-Modular Algorithm (SMA) for solving difference of submodular functions and SMA is proved to converge to local optimal. Further, we present an randomized algorithm based on weighted group coverage maximization for GPM and apply Sandwich framework to get theoretical results. Our experiments verify the effectiveness of our method, as well as the advantage of our method against the other heuristic methods.