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

摘要：

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

关键词：社会网络;影响力传播;成本最小;抽样;种子

所属期刊栏目：42

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目;江苏省自然科学基金项目;江苏省教育厅自然科学基金项目;江苏省六大人才高峰基金项目;江苏省高等职业院校专业带头人高端研修基金项目;扬州市科技计划软科学研究基金项目;扬州市职业大学校级重点科研基金项目

在线出版日期：2021-08-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2195-2202