Seed activation scheduling for influence maximization in social networks
Seed activation scheduling for influence maximization in social networks
复制标题
DOI：
10.1016/j.omega.2017.06.002
复制
发表时间：
2017-06
期刊：
影响因子：
--
通讯作者：
Mohammadreza Samadi;R. Nagi;Alexander Semenov;Alexander G. Nikolaev
中科院分区：
文献类型：
--
作者：
Mohammadreza Samadi;R. Nagi;Alexander Semenov;Alexander G. Nikolaev
本文通过利用被称为“种子”的级联传播器，解决了在社交网络中战略性地最大化影响力传播的挑战。它引入了种子激活调度问题（SASP），在给定的预算下，在给定的时间范围内，在存在/不存在竞争的情况下，选择种子激活的时间。SASP的框架是一个以博客为中心的营销问题，在一个两级网络上，决定在计算好的时间点购买知名博客的赞助文章。贝叶斯证据扩散模型-部分并行级联（PPC）模型-允许网络节点部分激活，与它们积累的证据水平成比例。PPC模型下的SASP被证明是NP-hard的。提出了一个用于SASP的混合整数程序，以及一个高效的列生成启发式算法。本文以网络营销为例，在现实环境中设置了其问题实例。基于在支持健康的论坛中观察到的用户交互，SASP解决方案在网络上实现了有利的最优性差距。所提出的分析强调了随着时间的推移，在点燃和维持影响级联时，早期和晚期种子激活之间的权衡。结果揭示了早期种子对于有利于长寿的运动的重要性，例如在服务业中，以及具有截止日期的运动的晚期种子的重要性，例如在政治竞争中。
This paper addresses the challenge of strategically maximizing the influence spread in a social network, by exploiting cascade propagators termed “seeds”. It introduces the Seed Activation Scheduling Problem (SASP) that chooses the timing of seed activation under a given budget, over a given time horizon, in the presence/absence of competition. The SASP is framed as a blogger-centric marketing problem on a two-level network, where the decisions are made to buy sponsored posts from prominent bloggers at calculated points in time. A Bayesian evidence diffusion model – the Partial Parallel Cascade (PPC) model – allows the network nodes to be partially activated, proportional to their accumulated evidence levels. The SASP under the PPC model is proven NP-hard. A mixed-integer program is presented for the SASP, along with an efficient column generation heuristic. The paper sets up its problem instances in real-world settings, taking web-based marketing as an application example. Favorable optimality gaps are achieved for SASP solutions on networks based on observed user interactions in pro-health discussion forums. The presented analyses highlight a trade-off between early and late seed activation in igniting and maintaining influence cascades over time. The results reveal the importance of early seeds for campaigns that favor longevity, e.g., in service industry, and the importance of late seeds for campaigns with deadline(s), e.g., in political competitions.