关键词: 网络影响最大化, 最小种子集, 简单多数阈值, 计数排序, BarabasiAlbert 网络

Abstract:

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.

Key words: network influence maximization；minimum seed set；simple majority threshold；counting sort；BarabasiAlbert network