基于抽样的影响力传播成本最小化算法

• 作者: 盛俊 李斌 陈崚
• 来源期刊: 计算机工程与设计
• 关键词: 社会网络 影响力传播 成本最小 抽样 种子
• 年，卷（期）: 2021,（8）
• 所属期刊栏目: 软件与算法|Software and Arithmetic
• 页码范围: 2195-2202
• 页数: 8页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.16208/j.issn1000-7024.2021.07.014

摘要

定义具有概率影响扩散保证的最小代价种子选择问题,验证了该问题是NP难的,且其影响函数是单调且次模的.将LT模型下的传播网络看成一个不确定图,对不确定图的可能世界进行抽样.为降低计算复杂度,提出一种对抽样图进行路径计数的算法来估计影响传播,使用VC维估计抽样图的数量.基于贪婪方法,提出一种求解该问题的算法,对该算法的误差进行分析.实验结果表明,该算法比其它方法具有更高的性能.