Search

Article

x

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

Identifying multiple influential nodes based on region density curve in complex networks

Kang Ling Xiang Bing-Bing Zhai Su-Lan Bao Zhong-Kui Zhang Hai-Feng

Identifying multiple influential nodes based on region density curve in complex networks

Kang Ling, Xiang Bing-Bing, Zhai Su-Lan, Bao Zhong-Kui, Zhang Hai-Feng
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • Complex networks are ubiquitous in natural science and social science, ranging from social and information networks to technological and biological networks. The roles of nodes in networks are often distinct, the most influential nodes often play an important role in understanding the spreading process and developing strategies to control epidemic spreading or accelerating the information diffusion. Therefore, identifying the influential nodes in complex networks has great theoretical and practical significance. Some centrality indices have been proposed to identify the influential nodes in recent years, but most of the existing algorithms are only appropriate to the identifying of single influential node. Many times, spreading process is initiated by simultaneously choosing multiple nodes as the spreading sources, such as rumors, opinions, advertisements, etc. Therefore, it is necessary to develop efficient methods of identifying the multiple influential nodes in complex networks. In this paper, a method based on region density curve of networks (RDC) is proposed to identify the multiple influential nodes in complex networks. Firstly, we rearrange all nodes of network in a new sequence, and then plot the region density curve for network. Finally, we identify the multiple influential nodes based on the valley points of region density curve. Using two kinds of spreading models, we compare RDC index with other indices in different real networks, such as degree, degree discount, k-shell, betweenness and their corresponding coloring methods. The results show that the influential nodes chosen according to our method are not only dispersively distributed, but also are relatively important nodes in networks. In addition, the time complexity of our method is low because it only depends on the local information of networks.
      Corresponding author: Bao Zhong-Kui, zkbao@ahu.edu.cn
    • Funds: Project supported by the Natural Science Foundation of Anhui Province, China (Grant No. 1808085MF201), the Natural Science Foundation of the Higher Education Institutions of Anhui Province, China (Grant No. KJ2017A025), the State Key Laboratory for Ocean Big Data Mining and Application of Zhejiang Province, China (Grant No. OBDMA201502), the Information Security Technology Collaborative Innovation Center of Anhui University, China (Grant No. ADXXBZ201608), and the Anhui University Foundation, China (Grant Nos. 01001951, 01005102).
    [1]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [2]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [3]

    Huang B, Zhao X Y, Qi K, Tang M, Do Y H (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218905]

    [4]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [5]

    Shu P P, Wang W, Tang T, Shang M S 2015 Acta Phys. Sin. 64 208901 (in Chinese) [舒盼盼, 王伟, 唐明, 尚明生 2015 物理学报 64 208901]

    [6]

    Liu Y, Tang M, Do Y H, Hui P M 2017 Phys. Rev. E 96 022323

    [7]

    Freeman L C 1979 Social Networks 1 215

    [8]

    Freeman L C 1977 Sociometry 40 35

    [9]

    Sabidussi G 1966 Psychometrika 31 581

    [10]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [11]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888

    [12]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [13]

    Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]

    [14]

    Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]

    [15]

    Radicchi F, Castellano C 2016 Phys. Rev. E 93 062314

    [16]

    Ruan Y R, Lao S Y, Wang J D, Bai L, Hou L L 2017 Acta Phys. Sin. 66 208901 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 候绿林 2017 物理学报 66 208901]

    [17]

    Bao Z K, Ma C, Xiang B B, Zhang H F 2017 Physica A 468 391

    [18]

    Hu Z L, Ren Z M, Yang G Y, Liu J G 2014 Int. J. Mod. Phys. C 25 1440013

    [19]

    Zhao X Y, Huang B, Tang M, Zhang H F, Chen D B 2015 Eur. Phys. Lett. 108 68005

    [20]

    Guo L, Lin J H, Guo Q, Liu J G 2016 Phys. Lett. A 380 837

    [21]

    Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos 28 013122

    [22]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [23]

    Chen W, Wang Y, Yang S 2009 Proceedings of the 15th International Conference on Knowledge Discovery and Data Mining Pairs, France, June 28-July 01, 2009 p199

    [24]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [25]

    Liu Y, Tang M, Zhou T, Do Y H 2015 Sci. Rep. 5 13172

    [26]

    Liu J G, Lin J H, Guo G, Zhou T 2016 Sci. Rep. 6 21380

    [27]

    Li R Q, Wang W, Shu P P, Yang H, Pan L M, Cui A X, Tang M (in Chinese) [李睿琪, 王伟, 舒盼盼, 杨慧, 潘黎明, 崔爱香, 唐明 2016 复杂系统与复杂性科学 3 1]

    [28]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

    [29]

    L L Y, Zhou T 2013 Link Prediction (Beijing:Higher Education Press) p286 (in Chinese) [吕琳媛, 周涛 2013 链路预测(北京:高等教育出版社) 第286页]

  • [1]

    Liu J G, Ren Z M, Guo Q, Wang B H 2013 Acta Phys. Sin. 62 178901 (in Chinese) [刘建国, 任卓明, 郭强, 汪秉宏 2013 物理学报 62 178901]

    [2]

    L L Y, Chen D B, Ren X L, Zhang Q M, Zhang Y C, Zhou T 2016 Phys. Rep. 650 1

    [3]

    Huang B, Zhao X Y, Qi K, Tang M, Do Y H (in Chinese) [黄斌, 赵翔宇, 齐凯, 唐明, 都永海 2013 物理学报 62 218905]

    [4]

    Ren X L, L L Y 2014 Chin. Sci. Bull. 59 1175 (in Chinese) [任晓龙, 吕琳媛 2014 科学通报 59 1175]

    [5]

    Shu P P, Wang W, Tang T, Shang M S 2015 Acta Phys. Sin. 64 208901 (in Chinese) [舒盼盼, 王伟, 唐明, 尚明生 2015 物理学报 64 208901]

    [6]

    Liu Y, Tang M, Do Y H, Hui P M 2017 Phys. Rev. E 96 022323

    [7]

    Freeman L C 1979 Social Networks 1 215

    [8]

    Freeman L C 1977 Sociometry 40 35

    [9]

    Sabidussi G 1966 Psychometrika 31 581

    [10]

    Bonacich P 1972 J. Math. Sociol. 2 113

    [11]

    Kitsak M, Gallos L K, Havlin S, Liljeros F, Muchnik L, Stanley H E, Makse H A 2010 Nature Phys. 6 888

    [12]

    Chen D B, L L Y, Shang M S, Zhang Y C, Zhou T 2012 Physica A 391 1777

    [13]

    Han Z M, Wu Y, Tan X S, Duan D G, Yang W J 2015 Acta Phys. Sin. 64 058902 (in Chinese) [韩忠明, 吴杨, 谭旭升, 段大高, 杨伟杰 2015 物理学报 64 058902]

    [14]

    Su X P, Song Y R 2015 Acta Phys. Sin. 64 020101 (in Chinese) [苏晓萍, 宋玉蓉 2015 物理学报 64 020101]

    [15]

    Radicchi F, Castellano C 2016 Phys. Rev. E 93 062314

    [16]

    Ruan Y R, Lao S Y, Wang J D, Bai L, Hou L L 2017 Acta Phys. Sin. 66 208901 (in Chinese) [阮逸润, 老松杨, 王竣德, 白亮, 候绿林 2017 物理学报 66 208901]

    [17]

    Bao Z K, Ma C, Xiang B B, Zhang H F 2017 Physica A 468 391

    [18]

    Hu Z L, Ren Z M, Yang G Y, Liu J G 2014 Int. J. Mod. Phys. C 25 1440013

    [19]

    Zhao X Y, Huang B, Tang M, Zhang H F, Chen D B 2015 Eur. Phys. Lett. 108 68005

    [20]

    Guo L, Lin J H, Guo Q, Liu J G 2016 Phys. Lett. A 380 837

    [21]

    Xiang B B, Bao Z K, Ma C, Zhang X Y, Chen H S, Zhang H F 2018 Chaos 28 013122

    [22]

    Zhao Z Y, Yu H, Zhu Z L, Wang X F (in Chinese) [赵之滢, 于海, 朱志良, 汪小帆 2014 计算机学报 37 753]

    [23]

    Chen W, Wang Y, Yang S 2009 Proceedings of the 15th International Conference on Knowledge Discovery and Data Mining Pairs, France, June 28-July 01, 2009 p199

    [24]

    Newman M E J 2004 Phys. Rev. E 69 066133

    [25]

    Liu Y, Tang M, Zhou T, Do Y H 2015 Sci. Rep. 5 13172

    [26]

    Liu J G, Lin J H, Guo G, Zhou T 2016 Sci. Rep. 6 21380

    [27]

    Li R Q, Wang W, Shu P P, Yang H, Pan L M, Cui A X, Tang M (in Chinese) [李睿琪, 王伟, 舒盼盼, 杨慧, 潘黎明, 崔爱香, 唐明 2016 复杂系统与复杂性科学 3 1]

    [28]

    Borge-Holthoefer J, Moreno Y 2012 Phys. Rev. E 85 026116

    [29]

    L L Y, Zhou T 2013 Link Prediction (Beijing:Higher Education Press) p286 (in Chinese) [吕琳媛, 周涛 2013 链路预测(北京:高等教育出版社) 第286页]

  • [1] Hu Qing-Cheng, Zhang Yong, Xu Xin-Hui, Xing Chun-Xiao, Chen Chi, Chen Xin-Hua. A new approach for influence maximization in complex networks. Acta Physica Sinica, 2015, 64(19): 190101. doi: 10.7498/aps.64.190101
    [2] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Hou Lü-Lin. An improved evaluating method of node spreading influence in complex network based on information spreading probability. Acta Physica Sinica, 2017, 66(20): 208901. doi: 10.7498/aps.66.208901
    [3] Wang Bing-Hong, Zhou Tao, Wang Wen-Xu, Li Ji, Jiang Pin-Qun. Growing complex network model with acceleratingly increasing number of nodes. Acta Physica Sinica, 2006, 55(8): 4051-4057. doi: 10.7498/aps.55.4051
    [4] Lü Ling, Zhang Chao. Chaos synchronization of a complex network with different nodes. Acta Physica Sinica, 2009, 58(3): 1462-1466. doi: 10.7498/aps.58.1462
    [5] Zhou Xuan, Zhang Feng-Ming, Li Ke-Wu, Hui Xiao-Bin, Wu Hu-Sheng. Finding vital node by node importance evaluation matrix in complex networks. Acta Physica Sinica, 2012, 61(5): 050201. doi: 10.7498/aps.61.050201
    [6] LÜ Ling, Liu Shuang, Zhang Xin, Zhu Jia-Bo, Shen Na, Shang Jin-Yu. Spatiotemporal chaos anti-synchronization of a complex network with different nodes. Acta Physica Sinica, 2012, 61(9): 090504. doi: 10.7498/aps.61.090504
    [7] Zhou Xuan, Zhang Feng-Ming, Zhou Wei-Ping, Zou Wei, Yang Fan. Evaluating complex network functional robustness by node efficiency. Acta Physica Sinica, 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
    [8] Liu Jin-Liang. Research on synchronization of complex networks with random nodes. Acta Physica Sinica, 2013, 62(4): 040503. doi: 10.7498/aps.62.040503
    [9] Han Zhong-Ming, Wu Yang, Tan Xu-Sheng, Duan Da-Gao, Yang Wei-Jie. Ranking key nodes in complex networks by considering structural holes. Acta Physica Sinica, 2015, 64(5): 058902. doi: 10.7498/aps.64.058902
    [10] Han Zhong-Ming, Chen Yan, Li Meng-Qi, Liu Wen, Yang Wei-Jie. An efficient node influence metric based on triangle in complex networks. Acta Physica Sinica, 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
    [11] Kong Jiang-Tao, Huang Jian, Gong Jian-Xing, Li Er-Yu. Evaluation methods of node importance in undirected weighted networks based on complex network dynamics models. Acta Physica Sinica, 2018, 67(9): 098901. doi: 10.7498/aps.67.20172295
    [12] Su Zhen, Gao Chao, Li Xiang-Hua. Analysis of the effect of node centrality on diffusion mode in complex networks. Acta Physica Sinica, 2017, 66(12): 120201. doi: 10.7498/aps.66.120201
    [13] Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya. Evaluating influential spreaders in complex networks by extension of degree. Acta Physica Sinica, 2015, 64(8): 088901. doi: 10.7498/aps.64.088901
    [14] Yu Hui, Liu Zun, Li Yong-Jun. Key nodes in complex networks identified by multi-attribute decision-making method. Acta Physica Sinica, 2013, 62(2): 020204. doi: 10.7498/aps.62.020204
    [15] Ren Zhuo-Ming, Liu Jian-Guo, Shao Feng, Hu Zhao-Long, Guo Qiang. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks. Acta Physica Sinica, 2013, 62(10): 108902. doi: 10.7498/aps.62.108902
    [16] Liu Jian-Guo, Ren Zhuo-Ming, Guo Qiang, Wang Bing-Hong. Node importance ranking of complex networks. Acta Physica Sinica, 2013, 62(17): 178901. doi: 10.7498/aps.62.178901
    [17] Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong. Node importance measurement based on neighborhood similarity in complex network. Acta Physica Sinica, 2017, 66(3): 038902. doi: 10.7498/aps.66.038902
    [18] Zhang Cong, Shen Hui-Zhang, Li Feng, Yang He-Qun. Multi-resolution density modularity for finding community structure in complex networks. Acta Physica Sinica, 2012, 61(14): 148902. doi: 10.7498/aps.61.148902
    [19] Yuan Wei-Guo, Liu Yun, Cheng Jun-Jun, Xiong Fei. Empirical analysis of microblog centrality and spread influence based on Bi-directional connection. Acta Physica Sinica, 2013, 62(3): 038901. doi: 10.7498/aps.62.038901
    [20] Su Xiao-Ping, Song Yu-Rong. Leveraging neighborhood “structural holes” to identifying key spreaders in social networks. Acta Physica Sinica, 2015, 64(2): 020101. doi: 10.7498/aps.64.020101
  • Citation:
Metrics
  • Abstract views:  537
  • PDF Downloads:  66
  • Cited By: 0
Publishing process
  • Received Date:  23 May 2018
  • Accepted Date:  27 June 2018
  • Published Online:  05 October 2018

Identifying multiple influential nodes based on region density curve in complex networks

    Corresponding author: Bao Zhong-Kui, zkbao@ahu.edu.cn
  • 1. School of Mathematical Science, Anhui University, Hefei 230601, China
Fund Project:  Project supported by the Natural Science Foundation of Anhui Province, China (Grant No. 1808085MF201), the Natural Science Foundation of the Higher Education Institutions of Anhui Province, China (Grant No. KJ2017A025), the State Key Laboratory for Ocean Big Data Mining and Application of Zhejiang Province, China (Grant No. OBDMA201502), the Information Security Technology Collaborative Innovation Center of Anhui University, China (Grant No. ADXXBZ201608), and the Anhui University Foundation, China (Grant Nos. 01001951, 01005102).

Abstract: Complex networks are ubiquitous in natural science and social science, ranging from social and information networks to technological and biological networks. The roles of nodes in networks are often distinct, the most influential nodes often play an important role in understanding the spreading process and developing strategies to control epidemic spreading or accelerating the information diffusion. Therefore, identifying the influential nodes in complex networks has great theoretical and practical significance. Some centrality indices have been proposed to identify the influential nodes in recent years, but most of the existing algorithms are only appropriate to the identifying of single influential node. Many times, spreading process is initiated by simultaneously choosing multiple nodes as the spreading sources, such as rumors, opinions, advertisements, etc. Therefore, it is necessary to develop efficient methods of identifying the multiple influential nodes in complex networks. In this paper, a method based on region density curve of networks (RDC) is proposed to identify the multiple influential nodes in complex networks. Firstly, we rearrange all nodes of network in a new sequence, and then plot the region density curve for network. Finally, we identify the multiple influential nodes based on the valley points of region density curve. Using two kinds of spreading models, we compare RDC index with other indices in different real networks, such as degree, degree discount, k-shell, betweenness and their corresponding coloring methods. The results show that the influential nodes chosen according to our method are not only dispersively distributed, but also are relatively important nodes in networks. In addition, the time complexity of our method is low because it only depends on the local information of networks.

Reference (29)

Catalog

    /

    返回文章
    返回