Viral Marketing for Digital Goods in Social Networks

摘要

Influence maximization is a problem of finding a small set of highly influential individuals in social networks to maximize the spread of influence. However, the distinction between the spread of influence and profit is neglected. The problem of profit maximization in social network extends the influence maximization problems to a realistic setting aiming to gain maximum profit in social networks. In this paper, we consider how to sell the digital goods (near zero marginal cost) by viral marketing in social network. The question can be modeled as a profit maximization problem. We show the problem is an unconstrained submodular maximization and adopt two efficient algorithms from two approaches. One is a famous algorithm from theoretical computer science and that can achieve a tight linear time (1/2) approximation. The second is to propose a profit discount heuristic which improves the efficiency. Through our extensive experiments, we demonstrate the efficiency and quality of the algorithms we applied. Based on results of our research, we also provide some advice for practical viral marketing.