Search

Article

x

留言板

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

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

Evaluating influential spreaders in complex networks by extension of degree

Min Lei Liu Zhi Tang Xiang-Yang Chen Mao Liu San-Ya

Citation:

Evaluating influential spreaders in complex networks by extension of degree

Min Lei, Liu Zhi, Tang Xiang-Yang, Chen Mao, Liu San-Ya
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • Evaluating influential spreaders in networks is of great significance for promoting the dissemination of beneficial information or inhibiting the spreading of harmful information. Currently, there are some central indices that can be used to evaluate spreading influence of {nodes}. However, most of them ignore the spreading probability and take into consideration only the network topology or the location of source node, so the excellent results can be achieved only when the spreading probability is in a specified range. For example, the degree centrality is appropriate for a minor spreading probability, but to ensure the accuracy, semi-local and closeness centralities are more suitable for a slightly larger one. To solve the sensitivity problem of spreading probability, a novel algorithm is proposed based on the extension of degree. In this algorithm, the coverage area of degree is recursively extended by the overlapping of degree of neighbors, which makes different extension levels correspond to different spreading probabilities. For a certain spreading probability, the proper level index is calculated by finding the most correlate ranking sequences of sampling {nodes}, which is obtained by matching the results of different spreading levels and SIR simulation. In this paper, the relationship between extension level and spreading probability is explained by the theory of fitting the weight and infected possibility of {nodes}, and the feasibility of the sampling method is verified by the computational experiments. The experimental results on both real and computer-generated datasets show that the proposed algorithm can effectively evaluate the spreading influences of {nodes} under different spreading probabilities, and the performance is close or even superior to that evaluated by using other central indices.
    • Funds: Project supported by the National Key Technology Research and Development Program of the Ministry of Science and Technology of China (Grant No. 2013BAH72B01), the Program for New Century Excellent Talents in University of Ministry of Education of China (Grant No. NCET-11-0654), and the Scientific Research Foundation of Ministry of Education of China and China Mobile Limited (Grant No. MCM20121061).
    [1]

    Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136

    [2]

    Newman M E J 2003 SIAM Rev. 45 167

    [3]

    Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47

    [4]

    Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101

    [5]

    Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527

    [6]

    Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904

    [7]

    Freeman L C 1978-1979 Soc. Networks 1 215

    [8]

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

    [9]

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

    [10]

    Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150

    [11]

    Bae J, Kim S 2014 Physica A 395 549

    [12]

    Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130

    [13]

    Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57

    [14]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]

    [15]

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

    [16]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [17]

    Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]

    [18]

    Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097

    [19]

    Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803

    [20]

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

    [21]

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

    [22]

    Kendall M G 1938 Biometrika 30 81

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [24]

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

    [25]

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

    [26]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [27]

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

    [28]

    Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122

    [29]

    Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [30]

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

  • [1]

    Zhang W, Bai S Y, Jin R 2014 Int. J. Mod. Phys. B 28 1450136

    [2]

    Newman M E J 2003 SIAM Rev. 45 167

    [3]

    Albert R, Barabasi A L 2002 Rev. Mod. Phys. 74 47

    [4]

    Wu Y, Hu Y, He X H, Deng K 2014 Chin. Phys. B 23 060101

    [5]

    Balthrop J, Forrest S, Newman M E J, Williamson M M 2004 Science 304 527

    [6]

    Li K Z, Xu Z P, Zhu G H, Ding Y 2014 Chin. Phys. B 23 118904

    [7]

    Freeman L C 1978-1979 Soc. Networks 1 215

    [8]

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

    [9]

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

    [10]

    Carmi S, Havlin S, Kirkpatrick S, Shavitt Y, Shir E 2007 Proc. Natl. Acad. Sci. USA 104 11150

    [11]

    Bae J, Kim S 2014 Physica A 395 549

    [12]

    Gao S, Ma J, Chen Z M, Wang G H, Xing C M 2014 Physica A 403 130

    [13]

    Du Y X, Gao C, Hu Y, Mahadevan S, Deng Y 2014 Physica A 399 57

    [14]

    Ren Z M, Liu J G, Shao F, Hu Z L, Guo Q 2013 Acta Phys. Sin. 62 108902 (in Chinese) [任卓明, 刘建国, 邵凤, 胡兆龙, 郭强 2013 物理学报 62 108902]

    [15]

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

    [16]

    Zeng A, Zhang C J 2013 Phys. Lett. A 377 1031

    [17]

    Liu Y, Tang M, Zhou T, Do Y 2014 arXiv:1409.5187v1 [physics. soc-ph]

    [18]

    Wang W, Tang M, Yang H, Do Y, Lai Y C, Lee G W 2014 Sci. Rep. 4 5097

    [19]

    Wang W, Tang M, Zhang H F, Gao H, Do Y, Liu Z H 2014 Phys. Rev. E 90 042803

    [20]

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

    [21]

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

    [22]

    Kendall M G 1938 Biometrika 30 81

    [23]

    Hu Q C, Yin Y S, Ma P F, Gao Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese) [胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 物理学报 62 140101]

    [24]

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

    [25]

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

    [26]

    Palla G, Derenyi I, Farkas I, Vicsek T 2005 Nature 435 814

    [27]

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

    [28]

    Boguna M, Pastor-Satorras R, Diaz-Guilera A, Arenas A 2004 Phys. Rev. E 70 056122

    [29]

    Castellano C, Pastor-Satorras R 2010 Phys. Rev. Lett. 105 218701

    [30]

    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] 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
    [4] 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
    [5] Luo Shi-Long, Gong Kai, Tang Chao-Sheng, Zhou Jing. A ranking approach based on k-shell decomposition method by filtering out redundant link in weighted networks. Acta Physica Sinica, 2017, 66(18): 188902. doi: 10.7498/aps.66.188902
    [6] Xu Ming, Xu Chuan-Yun, Cao Ke-Fei. Effect of degree correlations on controllability of undirected networks. Acta Physica Sinica, 2017, 66(2): 028901. doi: 10.7498/aps.66.028901
    [7] 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
    [8] 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
    [9] 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
    [10] Ouyang Bo, Jin Xin-Yu, Xia Yong-Xiang, Jiang Lu-Rong, Wu Duan-Po. Dynamic interplay between epidemics and cascades:Epidemic outbreaks in uncorrelated networks. Acta Physica Sinica, 2014, 63(21): 218902. doi: 10.7498/aps.63.218902
    [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] 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
    [14] 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
    [15] 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
    [16] 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
    [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] Yan Xiao-Yong, Wang Ming-Sheng. Influence of growth speed on the actors’ degree distribution of collaboration networks. Acta Physica Sinica, 2010, 59(2): 851-858. doi: 10.7498/aps.59.851
    [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:  8544
  • PDF Downloads:  658
  • Cited By: 0
Publishing process
  • Received Date:  04 September 2014
  • Accepted Date:  17 November 2014
  • Published Online:  05 April 2015

/

返回文章
返回