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