Cascades and Overexposure in Social Networks: The Budgeted Case
Cascades and Overexposure in Social Networks: The Budgeted Case
复制标题
DOI：
10.5555/3535850.3535923
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
M. Irfan;Kim Hancock;L. Friel
中科院分区：
文献类型：
--
作者：
M. Irfan;Kim Hancock;L. Friel
影响力最大化（IM）现在已经成为一个广泛研究的话题，但直到最近几年才有研究考虑过度暴露。过度曝光通常被衡量为在信息级联过程中与到达非预期接收者相关的负成本。当我们可以根据需要播种任意数量的节点时，多项式时间算法因具有过度曝光的级联而闻名。本文重点关注预算播种案例的过度曝光，这一点几乎没有受到关注。我们表明，即使对于受限情况，该问题也是 NP 困难的。针对各种特殊情况，我们设计了可证明的近似算法、动态规划解决方案、线性规划解决方案和启发式方法。对于一般情况，我们提供了一个线性编程解决方案和几种快速有效的启发式方法，其中大部分是贪婪的风格。我们使用合成网络和现实世界网络进行了广泛的实验研究。我们研究网络属性和模型参数如何影响我们的算法。它带来了有趣的发现，例如为什么低质量的产品需要更智能的算法，以及为什么某些算法在某些网络上表现良好，但在其他网络上表现不佳。
Influence maximization (IM) has now been a widely studied topic, but only in recent years have studies considered overexposure. Overexposure is usually measured as the negative cost associated with reaching unintended recipients during an information cascade. A polynomial-time algorithm is known for cascades with overex-posure when we can seed as many nodes as we want. This paper focuses on overexposure for the budgeted case of seeding, which has received little to no attention. We show that the problem is NP-hard even for restricted cases. For various special cases, we devise provable approximation algorithms, dynamic programming solutions, linear programming solutions, and heuristics. For the general case, we provide a linear programming solution and several fast and effective heuristics, mostly of the greedy flavor. We perform an extensive experimental study using synthetic and real-world networks. We investigate how network properties and model parameters impact our algorithms. It brings out interesting findings like why a low-quality product needs a smarter algorithm, and why certain algorithms do well on some networks but not others.