《计算机学报》文章摘要   全文下载
文章题目	一种新型的社会网络影响最大化算法
作者	田家堂 王轶彤 冯小军
作者单位	(复旦大学计算机科学技术学院 上海 201203)
发表年份	2011
发表月份	10期(1956—1965)
文章摘要	摘要 社会网络中影响最大化问题是对于给定k值,寻找k个具有最大影响范围的节点集.这是一个优化问题并且是NP-完全的.Kemple和Kleinberg提出具有较好影响范围的贪心算法，但其时间复杂度很高，不能适用在大型社会网络中，并且不能保证最好的影响范围.文中利用线性阈值模型的“影响力积累”特性，提出了一个该模型下影响最大化算法的框架，并在此框架基础上给出一个新的算法HPG.HPG综合考虑网络的结构特性和传播特性，首先启发式选择PI值最大的节点，然后寻找最具影响力的节点.实验结果显示HPG在最终影响范围和运行时间上都获得比贪心算法更好的效果. 关键词 社会网络；贪心算法；影响最大化；带符号网络；信息传播 中图法分类号 TP311 DOI号: 10.3724/SP.J.1016.2011.01956