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

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

A greedy algorithm for minimum seed set based on counting sort

The Minimum Seed Set (MSS) problem is related to the network influence maximization. The study of the MSS problem desires discovering the smallest possible set of nodes such that, if initially activated, the influence guarantees spreading to the entire network under a given threshold model. For computing MSS in a network with node thresholds, a new greedy algorithm is proposed based on counting sort,which sorts nodes of the network at first by the key values of node degrees minus its thresholds and then processes the current nodes with the minimum key values.The time complexity of the new algorithm is analyzed, which improves the method based on minimum heap.The upper bound on the average size of calculated seed sets in classic scale free BA networks is produced under simple majority threshold. The experimental results on synthetic and real world datasets show that the proposed approach is efficient and especially it can find smaller size of seed set in scale free networks than the related algorithm counterpart.