Overlapping influence of multiple spreaders in complex networks

doi:10.3969/j.issn.0253-2778.2016.01.005

Abstract

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

CLC Number:

O414

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.

References

［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]	MENG Fei, PAN Ziwen, YE Bangjiao. Simulation of the implantation of slow positron beams into metallic materials based on Geant4 [J]. Journal of University of Science and Technology of China, 2020, 50(2): 236-242.
[2]	QI Fangpeng, WANG Tong, FU Zhongqian. Link prediction in complex networks based on mutual information [J]. Journal of University of Science and Technology of China, 2020, 50(1): 57-63.
[3]	LIU Yan, RAO Yuan. A new method node importance evaluation based on multi-domain topology characteristics in complex networks [J]. Journal of University of Science and Technology of China, 2019, 49(7): 533-543.
[4]	SUN Gengxin, BIN Sheng. Network public opinion propagation model based on interest matching in multiple relationship social network [J]. Journal of University of Science and Technology of China, 2018, 48(9): 730-738.
[5]	YU Zhisong, YU Ziyang, FAN Hongyi. The source of diffusion equation and amplitude attenuation equation of density matrix by using coherent state representation [J]. Journal of University of Science and Technology of China, 2018, 48(5): 374-377.
[6]	YAN Ye, JIANG Nianpeng, ZHANG Haitao. Experimental investigation on the effect of dilution on the #br#liftoff and blowout characteristics of jet diffusion flame [J]. Journal of University of Science and Technology of China, 2018, 48(3): 246-252.
[7]	ZHANG Miao, SONG Wenhua, LIU Xingna, WEI Dong, HUANG Xin. Effect of fireproof clogging on combustion resistent property of external thermal insulation systems with curtain walls [J]. Journal of University of Science and Technology of China, 2015, 45(9): 784-794.
[8]	LOU Bo, XU Jianhong, LIN Zhenguan, XU Yi. Fractal structure characteristic of the diffusion flame of moving fire on linear motion [J]. Journal of University of Science and Technology of China, 2013, 43(8): 679-686.
[9]	HUANG Xianjia, TU Ran, YI Jianxin, XIE Qiyuan, JIANG Xi. The main scientific challenges in fire safety research of nuclear power plants [J]. Journal of University of Science and Technology of China, 2013, 43(11): 959-966.
[10]	HOU Zerong, WAN Lei, BAI Zhizhong, WANG Deliang. Effect of CdCl2 annealing treatment on interdiffusion and reaction at the CdS/CdTe interface [J]. Journal of University of Science and Technology of China, 2010, 40(7): 718-726.
[11]	WU Wen, HUANG Wei, ZHAO Pinghui, YE Taohong. Study of RANS based flamelet/progress variable turbulent combustion model [J]. Journal of University of Science and Technology of China, 2010, 40(10): 1016-1022.