基于计数排序的最小种子集贪心算法

摘要

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