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

J4 ›› 2014, Vol. 36 ›› Issue (06): 1057-1063.

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

赵学锋1，陈祥恩2

(1.西北师范大学计算机科学与工程学院,甘肃兰州 730070；
2. 西北师范大学数学与统计学院,甘肃兰州 730070)

收稿日期:2013-02-17 修回日期:2013-05-08 出版日期:2014-06-25 发布日期:2014-06-25
基金资助:
国家自然科学基金资助项目（61163037）

A greedy algorithm for minimum
seed set based on counting sort

ZHAO Xuefeng1,CHEN Xiangen2

(1.College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070；
2.College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,China)

Received:2013-02-17 Revised:2013-05-08 Online:2014-06-25 Published:2014-06-25

摘要/Abstract

摘要：

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

关键词: 网络影响最大化, 最小种子集, 简单多数阈值, 计数排序, 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

赵学锋1，陈祥恩2. 基于计数排序的最小种子集贪心算法[J]. J4, 2014, 36(06): 1057-1063.

ZHAO Xuefeng1,CHEN Xiangen2. A greedy algorithm for minimum
seed set based on counting sort [J]. J4, 2014, 36(06): 1057-1063.

参考文献

［1］Kempe D, Kleinberg J, Tardos E. Maximizing the spread of influence through a social network［C］∥Proc of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003:137146.
［2］Chen N.On the approximability of influence in social networks［J］. Journal of Discrete Optimization, 2009, 23 (3):14001415.
［3］BenZwi O, Hermelin D, Lokshtanov D, et al. Treewidth governs the complexity of target set selection ［J］. Discrete Optimization, 2011, 8 (1):8796.
［4］Chen W, Wang Y J, Yang S Y. Efficient influence maximization in social networks［C］∥Proc of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2009:199208.
［5］Ackerman E, BenZwi O,Wolfovits G. Combinatorial model and bounds for target set selection［J］.Theoretical Computer Science, 2010, 411(4446):40174022.
［6］Chang C L, Lyuu Y D. Spreading messages［J］. Theoretical Computer Science, 2009, 410 (2729):27142724.
［7］Chang C L, Lyuu Y D. On irreversible dynamic monopolies in general graphs［EB/OL］.［20121005］. http://arxiv.org/abs/0904.2306.
［8］Shakarian P, Paulo D. Large social networks can be targeted for viral marketing with small seed sets［C］∥Proc of IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), 2012:18.
［9］Cormen T H, Leiserson C E, Rivest R L, et al. Introduction to algorithms［M］. 2nd ed. Cambridge:MIT Press, 2001.
［10］Sedgewick R. Algorithms in Java, Part 5:Graph algorithms［M］. 3rd ed. MA:AddisonWesley, 2004.
［11］Clauset A, Shalizi A, Newman M. Powerlaw distribution in empirical data［J］. SIAM Review, 2009, 51(4):661703.
［12］Balabasi A L, Albert R. Emergence of scaling in random networks ［J］. Science, 1999, 286 (5439):509512.
［13］Wang Xiaofan, Li Xiang, Chen Guanrong. Complex networks:Theory and applications［M］. Beijing:Tsinghua University Press, 2006. (in Chinese)
［14］Wang L, Lou T, Tang J, et al. Detecting community kernels in large social networks［C］∥Proc of the 11th IEEE International Conference on Data Mining (ICDM), 2011:784793.
附中文参考文献：
［13］汪小帆，李翔，陈关荣．复杂网络理论及其应用［M］. 北京:清华大学出版社, 2006.