Search

Article

x

留言板

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

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

An improved evaluating method of node spreading influence in complex network based on information spreading probability

Ruan Yi-Run Lao Song-Yang Wang Jun-De Bai Liang Hou Lü-Lin

Citation:

An improved evaluating method of node spreading influence in complex network based on information spreading probability

Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Hou Lü-Lin
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • How to evaluate the node spreading ability and how to find influential nodes in complex networks are crucial to controlling diseases and rumors, accelerating or hindering information from diffusing, and designing effective advertising strategies for viral marketing, etc. At present, many indicators based on the shortest path, such as closeness centrality, betweenness centrality and the (SP) index have been proposed to evaluate node spreading influence. The shortest path indicates that the information transmission path between nodes always selects the optimal mode. However, information does not know the ideal route from one place to another. The message does not flow only along geodesic paths in most networks, and information transmission path may be any reachable path between nodes. In the network with high clustering coefficient, the local high clustering of the nodes is beneficial to the large-scale dissemination of information. If only the information is transmitted according to the optimal propagation mode, which is the shortest path propagation, the ability to disseminate the node information would be underestimated, and thus the sorting precision of node spreading influence is reduced. By taking into account the transmission rate and the reachable path between a node and its three-step inner neighbors, we design an improved method named ASP to generate ranking list to evaluate the node spreading ability. We make use of the susceptible-infected-recovered (SIR) spreading model with tunable transmission rate to check the effectiveness of the proposed method on six real-world networks and three artificial networks generated by the Lancichinetii-Fortunato-Radicchi (LFR) benchmark model. In the real data sets, the proposed algorithm can achieve a better result than other metrics in a wide range of transmission rate, especially in networks with high clustering coefficients. The experimental results of the three LFR benchmark datasets show that the relative accuracy of ranking result of the ASP index and the SP index changes with the sparseness of the network and the information transmission rate. When the information dissemination rate is small, SP index is slightly better than the ASP index. The reason for this result is that when the transmission rate is small, the node influence is close to the degree. However, when the transmission rate is greater, the accuracy of the ASP index is higher than those of other indicators. This work can shed light on how the local clustering exerts an influence on the node propagation.
      Corresponding author: Ruan Yi-Run, ruanyirun@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61302144, 61603408).
    [1]

    Dorogovtsev S N, Mendes J F F, Samukhin A N 2000 Phys. Rev. Lett. 85 4633

    [2]

    L L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 59 1

    [3]

    Papadopoulos F, Kitsak M, Serrano M A, Boguna M, Krioukov D 2012 Nature 489 537

    [4]

    Tang J, Piera M A, Guasch T 2016 Transport Res. C 67 357

    [5]

    Barabsi A L, Albert R 1999 Science 286 509

    [6]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [7]

    L L Y, Chen D B, Zhou T 2011 New J. Phys. 13 123005

    [8]

    Medo M, Zhang Y C, Zhou T 2009 Europhys. Lett. 88 38005

    [9]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [10]

    Albert R, Barabsi A L 2002 Rev. Modern Phys. 74 47

    [11]

    Castellano C, Fortunato S, Loreto V 2009 Rev. Modern Phys. 81 591

    [12]

    Yang J, Yao C, Ma W, Chen G 2010 Physica A 389 859

    [13]

    Morone F, Makse H A 2015 Nature 524 65

    [14]

    Zhang J X, Chen D B, Zhao Z D 2016 Sci. Rep. 6

    [15]

    Albert R, Jeong H, Barabsi A L 1999 Nature 401 130

    [16]

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

    [17]

    Stephenson K, Zelen M 1989 Soc. Netw. 1 11

    [18]

    Borgatti S P 2005 Soc. Netw. 27 55

    [19]

    Sabidussi G 1966 Psychometrika 31 581

    [20]

    Freeman L C 1977 Sociometry 40 35

    [21]

    Kleinberg J M 1999 JACM 46 604

    [22]

    Brin S, Page L 1998 Comput. Networks. Isdn. 30 107

    [23]

    Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103

    [24]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS ONE 6 e21202

    [25]

    L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [26]

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

    [27]

    Bae J, Kim S 2014 Physica A 395 549

    [28]

    Liu Y, Tang M, Zhou T, Do Y 2016 Physica A 452 289

    [29]

    Duan J M, Shang M S, Cai S M, Zhang Y X 2015 Acta Phys. Sin. 64 200501 (in Chinese)[段杰明, 尚明生, 蔡世民, 张玉霞2015物理学报64 200501]

    [30]

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

    [31]

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

    [32]

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

    [33]

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

    [34]

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

    [35]

    Newman M E J 2005 Soc. Netw. 27 39

    [36]

    Fowler J H, Christakis N A 2008 Br. Med. J. 337 a2338

    [37]

    Newman M E J 2002 Phys. Rev. E 66 016128

    [38]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [39]

    Kendall M G 1945 Biometrika 33 239

    [40]

    Knight W R 1966 J. Amer. Statist. Assoc. 61 436

    [41]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [42]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [43]

    Jeong H, Mason S P, Barabasi A, Oltvai Z N 2001 Nature 1 41

    [44]

    Xie N 2006 M.S. Dissertation (Bristol:University of Bristol)

    [45]

    Spring N, Mahajan R, Wetherall D 2002 IEEEACM Trans. Netw. 1 2

    [46]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1]

    Dorogovtsev S N, Mendes J F F, Samukhin A N 2000 Phys. Rev. Lett. 85 4633

    [2]

    L L Y, Medo M, Yeung C H, Zhang Y C, Zhang Z K, Zhou T 2012 Phys. Rep. 59 1

    [3]

    Papadopoulos F, Kitsak M, Serrano M A, Boguna M, Krioukov D 2012 Nature 489 537

    [4]

    Tang J, Piera M A, Guasch T 2016 Transport Res. C 67 357

    [5]

    Barabsi A L, Albert R 1999 Science 286 509

    [6]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [7]

    L L Y, Chen D B, Zhou T 2011 New J. Phys. 13 123005

    [8]

    Medo M, Zhang Y C, Zhou T 2009 Europhys. Lett. 88 38005

    [9]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [10]

    Albert R, Barabsi A L 2002 Rev. Modern Phys. 74 47

    [11]

    Castellano C, Fortunato S, Loreto V 2009 Rev. Modern Phys. 81 591

    [12]

    Yang J, Yao C, Ma W, Chen G 2010 Physica A 389 859

    [13]

    Morone F, Makse H A 2015 Nature 524 65

    [14]

    Zhang J X, Chen D B, Zhao Z D 2016 Sci. Rep. 6

    [15]

    Albert R, Jeong H, Barabsi A L 1999 Nature 401 130

    [16]

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

    [17]

    Stephenson K, Zelen M 1989 Soc. Netw. 1 11

    [18]

    Borgatti S P 2005 Soc. Netw. 27 55

    [19]

    Sabidussi G 1966 Psychometrika 31 581

    [20]

    Freeman L C 1977 Sociometry 40 35

    [21]

    Kleinberg J M 1999 JACM 46 604

    [22]

    Brin S, Page L 1998 Comput. Networks. Isdn. 30 107

    [23]

    Radicchi F, Fortunato S, Markines B, Vespignani A 2009 Phys. Rev. E 80 056103

    [24]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PLoS ONE 6 e21202

    [25]

    L L Y, Zhou T, Zhang Q M, Stanley H E 2016 Nat. Commun. 7 10168

    [26]

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

    [27]

    Bae J, Kim S 2014 Physica A 395 549

    [28]

    Liu Y, Tang M, Zhou T, Do Y 2016 Physica A 452 289

    [29]

    Duan J M, Shang M S, Cai S M, Zhang Y X 2015 Acta Phys. Sin. 64 200501 (in Chinese)[段杰明, 尚明生, 蔡世民, 张玉霞2015物理学报64 200501]

    [30]

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

    [31]

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

    [32]

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

    [33]

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

    [34]

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

    [35]

    Newman M E J 2005 Soc. Netw. 27 39

    [36]

    Fowler J H, Christakis N A 2008 Br. Med. J. 337 a2338

    [37]

    Newman M E J 2002 Phys. Rev. E 66 016128

    [38]

    Pastor-Satorras R, Vespignani A 2001 Phys. Rev. Lett. 86 3200

    [39]

    Kendall M G 1945 Biometrika 33 239

    [40]

    Knight W R 1966 J. Amer. Statist. Assoc. 61 436

    [41]

    Newman M E J 2006 Phys. Rev. E 74 036104

    [42]

    Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A 2003 Phys. Rev. E 68 065103

    [43]

    Jeong H, Mason S P, Barabasi A, Oltvai Z N 2001 Nature 1 41

    [44]

    Xie N 2006 M.S. Dissertation (Bristol:University of Bristol)

    [45]

    Spring N, Mahajan R, Wetherall D 2002 IEEEACM Trans. Netw. 1 2

    [46]

    Lancichinetti A, Fortunato S, Radicchi F 2008 Phys. Rev. E 78 046110

  • [1] Li Jiang, Liu Ying, Wang Wei, Zhou Tao. Identifying influential nodes in spreading process in higher-order networks. Acta Physica Sinica, 2024, 73(4): 048901. doi: 10.7498/aps.73.20231416
    [2] Ruan Yi-Run, Lao Song-Yang, Tang Jun, Bai Liang, Guo Yan-Ming. Node importance ranking method in complex network based on gravity method. Acta Physica Sinica, 2022, 71(17): 176401. doi: 10.7498/aps.71.20220565
    [3] 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
    [4] Li Yong-Jun, Yin Chao, Yu Hui, Liu Zun. Link prediction in microblog retweet network based on maximum entropy model. Acta Physica Sinica, 2016, 65(2): 020501. doi: 10.7498/aps.65.020501
    [5] 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
    [6] Wu Teng-Fei, Zhou Chang-Le, Wang Xiao-Hua, Huang Xiao-Xi, Chen Zhi-Qun, Wang Rong-Bo. Microblog propagation network model based on mean-field theory. Acta Physica Sinica, 2014, 63(24): 240501. doi: 10.7498/aps.63.240501
    [7] Liu Shu-Xin, Ji Xin-Sheng, Liu Cai-Xia, Guo Hong. A complex network evolution model for network growth promoted by information transmission. Acta Physica Sinica, 2014, 63(15): 158902. doi: 10.7498/aps.63.158902
    [8] Deng Qi-Xiang, Jia Zhen, Xie Meng-Shu, Chen Yan-Fei. Study of directed networks-based Email virus propagation model and its concussion attractor. Acta Physica Sinica, 2013, 62(2): 020203. doi: 10.7498/aps.62.020203
    [9] Li Zhao, Xu Guo-Ai, Ban Xiao-Fang, Zhang Yi, Hu Zheng-Ming. Complex information system security risk propagation research based on cellular automata. Acta Physica Sinica, 2013, 62(20): 200203. doi: 10.7498/aps.62.200203
    [10] Hu Qing-Cheng, Yin Yan-Shen, Ma Peng-Fei, Gao Yang, Zhang Yong, Xing Chun-Xiao. A new approach to identify influential spreaders in complex networks. Acta Physica Sinica, 2013, 62(14): 140101. doi: 10.7498/aps.62.140101
    [11] 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
    [12] 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
    [13] Xiong Xi, Hu Yong. Research on the dynamics of opinion spread based on social network services. Acta Physica Sinica, 2012, 61(15): 150509. doi: 10.7498/aps.61.150509
    [14] Fu Bai-Bai, Gao Zi-You, Lin Yong, Wu Jian-Jun, Li Shu-Bin. The analysis of traffic congestion and dynamic propagation properties based on complex network. Acta Physica Sinica, 2011, 60(5): 050701. doi: 10.7498/aps.60.050701
    [15] Wang Ya-Qi, Jiang Guo-Ping. Epidemic spreading in complex networks with spreading delay based on cellular automata. Acta Physica Sinica, 2011, 60(8): 080510. doi: 10.7498/aps.60.080510
    [16] Song Yu-Rong, Jiang Guo-Ping. Epidemic-spreading model for networks with different anti-attack abilities of nodes and nonuniform transmission of edges. Acta Physica Sinica, 2010, 59(11): 7546-7551. doi: 10.7498/aps.59.7546
    [17] Wang Ya-Qi, Jiang Guo-Ping. Virus spreading on complex networks with imperfect immunization. Acta Physica Sinica, 2010, 59(10): 6734-6743. doi: 10.7498/aps.59.6734
    [18] Ni Shun-Jiang, Weng Wen-Guo, Fan Wei-Cheng. Spread dynamics of infectious disease in growing scale-free networks. Acta Physica Sinica, 2009, 58(6): 3707-3713. doi: 10.7498/aps.58.3707
    [19] Song Yu-Rong, Jiang Guo-Ping. Research of malware propagation in complex networks based on 1-D cellular automata. Acta Physica Sinica, 2009, 58(9): 5911-5918. doi: 10.7498/aps.58.5911
    [20] Xu Dan, Li Xiang, Wang Xiao-Fan. An investigation on local area control of virus spreading in complex networks. Acta Physica Sinica, 2007, 56(3): 1313-1317. doi: 10.7498/aps.56.1313
Metrics
  • Abstract views:  6810
  • PDF Downloads:  364
  • Cited By: 0
Publishing process
  • Received Date:  19 May 2017
  • Accepted Date:  04 July 2017
  • Published Online:  05 October 2017

/

返回文章
返回