大规模网络中多传播源的重叠影响力问题研究

doi:10.3969/j.issn.0253-2778.2016.01.005

中国科学技术大学学报 ›› 2016, Vol. 46 ›› Issue (1): 28-35.DOI: 10.3969/j.issn.0253-2778.2016.01.005

• 论著 • 上一篇

大规模网络中多传播源的重叠影响力问题研究

周明洋，付忠谦*，廖好

1.中国科技大学电子科学与技术系，安徽合肥 230027；2.深圳大学计算机系，广东深圳 518060

收稿日期:2015-08-27 修回日期:2015-09-29 接受日期:2015-09-29 出版日期:2015-09-29 发布日期:2015-09-29
通讯作者: 傅忠谦
作者简介:周明洋，男，1987年生，博士生. 研究方向：复杂网络、网络控制及数据挖掘. E-mail: zmy123@mail.ustc.edu.cn

Overlapping influence of multiple spreaders in complex networks

ZHOU Mingyang, FU Zhong qian*, LIAO Hao

1. Department of Electronic Science and Technology, University of Science and Technology of China, Hefei 230027, China; 2. Department of Computer Science,Shenzhen University, Shenzhen, 518060

Received:2015-08-27 Revised:2015-09-29 Accepted:2015-09-29 Online:2015-09-29 Published:2015-09-29

摘要/Abstract

摘要： 计算机和Internet的快速发展推动了网络科学的研究.信息传播是网络研究领域的热点，信息传播的一个关键问题是初始信息源的选择，传统的方法通过衡量节点重要性的指标（节点度、介数、邻居节点的重要性等），然后根据单一节点的重要性从大到小排序，依次选择重要节点.针对单一节点的传播能力，传统的方法具有很好的效果，但是在多传播源选择时效果并不好.本文首先分析了传统方法的不足，并指出多节点的综合影响力没有提高是由于节点影响力的重叠效应.在此基础上，本文提出了一个衡量多节点综合影响力的指标，然后通过贪婪算法选择多个传播源节点.实际网络上的仿真实验表明，针对传染病模型（SIR），本文提出的方法能够选择更优的多传播源节点.进一步研究发现这些驱动节点间的平均距离更大，稀疏性更高，表明增加传播源节点的稀疏性能够降低节点的重叠影响力，因此综合影响力得到提高.

关键词: 传播, 扩散, 节点影响力, 复杂网络

Abstract: With the development of computer technology and the Internet, network science is attracting many scientists from various fields. One field in network science is epidemic spreading, in which the key problem is the selection of source spreaders. Conventional methods select spreaders according to the importance of nodes (degree, betweenness and so on) and nodes with high importance are selected. Traditional methods perform well in characterizing the spreading ability of single nodes, but poorly in multiple nodes. An anahysis is made and the reasons poor performance of multiple spreaders is attributed to the overlapping influences that decrease the overall spreading ability of multiple nodes. Then, an improved method is proposed to suppress the overlapping influences. The validity of the proposed method is illustrated in four real-world networks in which the method could select better multiple spreaders. Further, it was found that improving the sparsity could reduce the overlapping influence of multiple spreaders, which enhances the overall spreading ability of nodes.

Key words: spreading, diffusion, influence of nodes, complex network

中图分类号:

O414

周明洋，付忠谦*，廖好. 大规模网络中多传播源的重叠影响力问题研究[J]. 中国科学技术大学学报, 2016, 46(1): 28-35.

ZHOU Mingyang, FU Zhong qian*, LIAO Hao. Overlapping influence of multiple spreaders in complex networks[J]. Journal of University of Science and Technology of China, 2016, 46(1): 28-35.

参考文献

［1］
Boccaletti, S., et al., Complex networks: Structure and dynamics. Physics reports, 2006. 424(4): p. 175-308.
[2] Strogatz S H. Exploring complex networks[J]. Nature, 2001. 410(6825): 268-276.
[3] Diekmann O, Heesterbeek J A P. Mathematical epidemiology of infectious diseases: Model building, analysis and interpretation[M]. Chichester: John Wiley & Sons, 2000.
[4] Chierichetti F, Lattanzi S, Panconesi A. Rumor spreading in social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2009: 375-386.
[5] Staniford S, Paxson V, Weaver N. How to own the internet in your spare time[C]// Proceedings of the 11th USENIX Security Symposium. Berkeley, USA: ACM Press, 2002:149-167.
[6] Kempe D, Kleinberg J, Tardos . Maximizing the spread of influence through a social network[C]// Proceedings of the 9th ACM SIGKDD International Conference on Knowledge discovery and Data Mining. Washington, USA: ACM Press, 2003: 137-146.
[7] Chen W, Wang Y, Yang S. Efficient influence maximization in social networks[C]// Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Paris, France: ACM Press, 2009: 199-208.
[8] 苏晓萍, 申情，宋玉蓉，等. 利用社会网络上最有影响力节点实现高效病毒营销[J]. 小型微型计算机系统, 2014. 35(8): 1803-1807.
Su Xiaoping, Shen Qing, Song Yurong, etal. Improving the efficiency of viral of marketing in a social network using influential nodes[J]. Jounal of Chinese Computer Systems,2014. 35(8): 1803-1807.
[9] Kempe D, Kleinberg J, Tardos . Influential nodes in a diffusion model for social networks[C]// International Colloquium on Automata, Languages and Programming. Springer, 2005: 1127-1138.
[10] Chen D B, Lü L Y, Shang M S, et al. Identifying influential nodes in complex networks[J]. Physica A: Statistical Mechanics and its Applications, 2012. 391(4): 1777-1787.
[11] Kitsak M, Gallos L K, Havlin S, et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010, 6(11): 888-893.
[12] Zeng A, Zhang C J. Ranking spreaders by decomposing complex networks[J]. Physics Letters A, 2013. 377(14): 1031-1035.
[13] Liu J G, Ren Z M, Guo Q. Ranking the spreading influence in complex networks. Physica A: Statistical Mechanics and its Applications, 2013. 392(18): 4154-4159.
[14] 任晓龙, 吕琳媛, 网络重要节点排序方法综述. 科学通报, 2014, 59(13): 1175-1197.
Ren Xiaolong,Lü Linyuan. Review of ranking nodes in complex networks[J]. Chinese Science Bulletin, 2014, 59(13): 1175-1197.
[15] 刘建国, et al., 复杂网络中节点重要性排序的研究进展. 物理学报, 2013. 62(17): p. 178901-178901.
[16] Chen D B, Gao H, Lü L, et al. Identifying influential nodes in large-scale directed networks: the role of clustering[J]. Plos One, 2013, 8(8): e77455.
[17] Cha M, Haddadi H, Benevenuto F, et al. Measuring user influence in twitter: The million follower fallacy[C]// Proceedinds of the 4th International Conference on Weblogs and Social Media. Washington, USA: ACM Press, 2010, 14: 30.
[18] Henderson K, Henderson K, Gallagher B, et al. Rolx: Structural role extraction & mining in large graphs[]CP// Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, China: ACM Press, 2012: 1231-1239.
[19] Bakshy E, Hohman J M, Mason W, et al. Everyone's an influencer: Quantifying influence on twitter[C]// Proceedings of the 4th ACM International Conference on Web Search and Data Mining. Hong Kong, China: ACM Press, 2011: 65-74.
[20] Hou B N, Yao Y P, Liao D B. Identifying all-around nodes for spreading dynamics in complex networks[J]. Physica A: Statistical Mechanics and Its Applications, 2012. 391(15): 4012-4017.
[21] Gao S, Ma J, Chen Z M, et al. Ranking the spreading ability of nodes in complex networks based on local structure[J]. Physica A: Statistical Mechanics and Its Applications, 2014, 403: 130-147.
[22] Fu Y H, Huang C Y, Sun C T. Identifying super-spreader nodes in complex networks[J]. Mathematical Problems in Engineering, 2015, 2015: 675713(1-8).
[23] Zou Y L, Chen G R. Choosing effective controlled nodes for scale-free network synchronization[J]. Physica A: Statistical Mechanics and its Applications, 2009. 388(14): 2931-2940.
[24] 汪小帆, 李翔, 陈关荣. 网络科学导论[J]. 北京: 高等教育出版社, 2012.
[25] Leskovec J, Krevl A. SNAP Datasets: Stanford Large Network Dataset Collection[EB/OL]. http://snap.stanford.edu/data.
[26] Song C M, Havlin S, Makse H A. Self-similarity of complex networks[J]. Nature, 2005, 433(7024): 392-395.
[27] Leskovec J, Lang K J, Dasgupta A, et al. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters[J]. Internet Mathematics, 2009. 6(1): 29-123.

()
()

[1]	李影, 孙天一, 金百锁, 张博. 在不同流动控制下欧洲COVID-19疫情的传播率[J]. 中国科学技术大学学报, 2021, 51(9): 654-670.
[2]	张文静，班志杰. 基于全局的引文网络影响力最大化算法[J]. 中国科学技术大学学报, 2020, 50(8): 1058-1063.
[3]	孟飞，潘子文，叶邦角. 基于Geant4的慢正电子束注入金属材料的模拟研究[J]. 中国科学技术大学学报, 2020, 50(2): 236-242.
[4]	丛爽, 吴文燊, 尚伟伟, 陈鼎. 削弱大气干扰影响的三种量子测距定位方案[J]. 中国科学技术大学学报, 2020, 50(1): 64-71.
[5]	齐方鹏, 王童, 傅忠谦. 基于互信息的复杂网络链路预测[J]. 中国科学技术大学学报, 2020, 50(1): 57-63.
[6]	刘雁，饶元. 基于多领域复杂网络拓扑结构的节点重要度评价方法[J]. 中国科学技术大学学报, 2019, 49(7): 533-543.
[7]	郭鹏，赵马杰，朱旻明，叶桃红. 自由圆射流对声激励的非线性响应分析[J]. 中国科学技术大学学报, 2019, 49(6): 465-475.
[8]	戴维佳，李乐天，周武旸. 基于期望传播的活跃用户检测和信道估计[J]. 中国科学技术大学学报, 2019, 49(10): 797-804.
[9]	孙更新，宾晟. 多关系社交网络中基于兴趣匹配的网络舆情传播模型[J]. 中国科学技术大学学报, 2018, 48(9): 730-738.
[10]	余之松，余子洋，范洪义. 用相干态表象论密度矩阵的扩散方程和振幅衰减方程的来源[J]. 中国科学技术大学学报, 2018, 48(5): 374-377.
[11]	严野，蒋年鹏，张海涛. 稀释对射流扩散火焰抬举及吹熄特性影响的实验研究[J]. 中国科学技术大学学报, 2018, 48(3): 246-252.
[12]	朱威，颜仕星，张磊，李国正. 基于真实世界临床数据的失眠病判别分析[J]. 中国科学技术大学学报, 2016, 46(10): 867-873.
[13]	胡锦银，贾晓峰. 广义屏波场模拟和成像的网格离散方案研究[J]. 中国科学技术大学学报, 2015, 45(2): 138-149.
[14]	朱红亚，陈昊东，王青松，孙金华. 多源重气泄漏扩散模拟研究[J]. 中国科学技术大学学报, 2014, 44(8): 697-703.
[15]	楼波，许建红，林振冠，徐毅. 直线运动下移动火源扩散火焰的分形结构特征[J]. 中国科学技术大学学报, 2013, 43(8): 679-686.

大规模网络中多传播源的重叠影响力问题研究

Overlapping influence of multiple spreaders in complex networks

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价