Revenue maximization by viral marketing: A social network host's perspective
Revenue maximization by viral marketing: A social network host's perspective
复制标题
DOI：
10.1109/icde.2016.7498227
复制
发表时间：
2016-05
期刊：
影响因子：
--
通讯作者：
Arijit Khan;Benjamin Zehnder;Donald Kossmann
中科院分区：
文献类型：
--
作者：
Arijit Khan;Benjamin Zehnder;Donald Kossmann
我们研究了一个社交网络主持人向多个竞争对手出售病毒式营销活动的收入最大化的新问题。每一位客户活动家都会告知社交网络主持人她在网络中的目标用户，以及如果她的目标用户之一购买了她的产品，她愿意向主持人支付多少钱。社交网络主持人反过来为她的每个客户活动家分配一组种子用户。为活动家设置的种子是有限数量的用户，活动家向这些用户提供免费样品、折扣价格等，期望这些种子用户会购买她的产品，并能够影响她在网络中的许多目标用户购买她的产品。由于各种产品采用成本，普通用户不太可能购买多个竞争产品。因此，从主持人的角度来看，重要的是将种子用户分配给客户活动家，以使种子分配确保主持人考虑到她的所有客户活动家的最大总收益。我们通过以下两个成熟的影响级联模型来描述我们的问题：独立级联模型和线性阈值模型。虽然我们使用这两个模型的问题都是NP难的，既不是单调的，也不是子模的；我们开发了具有理论性能保证的近似算法。然而，由于我们的近似算法通常会导致更高的运行时间，我们还设计了有效的启发式方法，在经验上与我们的近似算法的性能一样好。我们详细的实验评估证明，所提出的技术是有效的，并且在真实数据集上是可伸缩的。
We study the novel problem of revenue maximization of a social network host that sells viral marketing campaigns to multiple competing campaigners. Each client campaigner informs the social network host about her target users in the network, as well as how much money she is willing to pay to the host if one of her target users buys her product. The social network host, in turn, assigns a set of seed users to each of her client campaigners. The seed set for a campaigner is a limited number of users to whom the campaigner provides free samples, discounted price etc. with the expectation that these seed users will buy her product, and would also be able to influence many of her target users in the network towards buying her product. Because of various product-adoption costs, it is very unlikely that an average user will purchase more than one of the competing products. Therefore, from the host's perspective, it is important to assign seed users to client campaigners in such a way that the seed assignment guarantees the maximum aggregated revenue for the host considering all her client campaigners. We formulate our problem by following two well-established influence cascading models: the independent cascade model and the linear threshold model. While our problem using both these models is NP-hard, and neither monotonic, nor sub-modular; we develop approximated algorithms with theoretical performance guarantees. However, as our approximated algorithms often incur higher running times, we also design efficient heuristic methods that empirically perform as good as our approximated algorithms. Our detailed experimental evaluation attests that the proposed techniques are effective and scalable over real-world datasets.