摘要：网络最小种子集问题与网络影响最大化问题相关,研究的是对于具有节点阈值的网络,构造网络的最小节点子集,使得如果这个子集中的节点是活的,则在给定的影响传播模型下整个网络都受到影响.为此提出了新的贪心算法,以节点的度与阈值的差为关键值对网络节点进行计数排序,然后取值最小的节点进行处理.新算法在时间复杂度上改进了基于最小堆的种子点选取算法.在简单多数阈值模型上针对经典的无标度网络得到了所构造的种子集规模上界.实验在随机生成网络和一些实际网络数据集上进行,结果表明所提方法的有效性,特别在无标度网络上生成的种子集具有比相关算法更小的规模.

关键词：网络影响最大化 最小种子集 简单多数阈值 计数排序 

单位：西北师范大学计算机科学与工程学院 甘肃兰州730070 西北师范大学数学与统计学院 甘肃兰州730070