[科普中国]-社交网络中的影响力阻断最大化

一．定义

影响力阻断最大化指的是当甲乙两种信息源同时在网络中竞争传播的情况下，给定一个传播模型，通过选择一定规模的属于甲的节点集，以使得与在没有甲竞争传播下相比，乙在甲竞争传播状态下的传播范围被阻断的最多，即阻断范围最大化1。

二．相关研究在使对方阻断最大化方面，C. Budak等人于2011年首次进行了研究，他们基于扩展的独立级联模型证明了竞争阻断最大化是NP-Hard问题，并将贪心算法同三种启发式算法进行了性能比较2。此外，He等人研究证明了竞争线性阈值模型下的信息阻断最大化问题符合子模特性，因此贪心算法具有近似保证，同时他们提出了基于LDAG的更为有效的启发式算法CLDAG来弥补贪心算法运行时长的不足3。