Search

Article

x

留言板

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

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

Node importance measurement based on neighborhood similarity in complex network

Ruan Yi-Run Lao Song-Yang Wang Jun-De Bai Liang Chen Li-Dong

Citation:

Node importance measurement based on neighborhood similarity in complex network

Ruan Yi-Run, Lao Song-Yang, Wang Jun-De, Bai Liang, Chen Li-Dong
PDF
Get Citation

(PLEASE TRANSLATE TO ENGLISH

BY GOOGLE TRANSLATE IF NEEDED.)

  • Ranking node importance is of great significance for studying the robustness and vulnerability of complex network. Over the recent years, various centrality indices such as degree, semilocal, K-shell, betweenness and closeness centrality have been employed to measure node importance in the network. Among them, some well-known global measures such as betweenness centrality and closeness centrality can achieve generally higher accuracy in ranking nodes, while their computation complexity is relatively high, and also the global information is not readily available in a large-scaled network. In this paper, we propose a new local metric which only needs to obtain the neighborhood information within two hops of the node to rank node importance. Firstly, we calculate the similarity of node neighbors by quantifying the overlap of their topological structures with Jaccard index; secondly, the similarity between pairs of neighbor nodes is calculated synthetically, and the redundancy of the local link of nodes is obtained. Finally, by reducing the influence of densely local links on ranking node importance, a new local index named LLS that considers both neighborhood similarity and node degree is proposed. To check the effectiveness of the proposed method of ranking node importance, we carry out it on six real world networks and one artificial small-world network by static attacks and dynamic attacks. In the static attack mode, the ranking value of each node is the same as that in the original network. In the dynamic attack mode, once the nodes are removed, the centrality of each node needs recalculating. The relative size of the giant component and the network efficiency are used for network connectivity assessment during the attack. A faster decrease in the size of the giant component and a faster decay of network efficiency indicate a more effective attack strategy. By comparing the decline rates of these two indices to evaluate the connectedness of all networks, we find that the proposed method is more efficient than traditional local metrics such as degree centrality, semilocal centrality, K-shell decomposition method, no matter whether it is in the static or dynamic manner. And for a certain ranking method, the results of the dynamic attack are always better than those of the static attack. This work can shed some light on how the local densely connections affect the node centrality in maintaining network robustness.
      Corresponding author: Ruan Yi-Run, ruanyirun@163.com
    • Funds: Project supported by the National Natural Science Foundation of China (Grant No. 61571453).
    [1]

    Barabási A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [3]

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

    [4]

    Rogers T 2015 Europhys. Lett. 109 28005

    [5]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [6]

    Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese)[王光增, 曹一家, 包哲静, 韩祯祥2009物理学报58 3597]

    [7]

    Albert R, Jeong H, Barabási A L 1999 Nature 401 130

    [8]

    Sabidussi G 1966 Psychometrika 31 581

    [9]

    Freeman L C 1977 Sociometry 40 35

    [10]

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

    [11]

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

    [12]

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

    [13]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

    [14]

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

    [15]

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

    [16]

    Wang J W, Rong L L, Guo T Z 2010 J. Dalian Univ. Technol. 50 822 (in Chinese)[王建伟, 荣莉莉, 郭天柱2010大连理工大学学报50 822]

    [17]

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

    [18]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc. Natl. Acad. Sci. 109 5962

    [19]

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

    [20]

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

    [21]

    Chen D B, Xiao R, Zeng A, Zhang Y C 2014 Europhys. Lett. 104 68006

    [22]

    Ruan Y R, Lao S Y, Xiao Y D, Wang J D, Bai L 2016 Chin. Phys. Lett. 33 028901

    [23]

    Burt R S 2009 Structure Holes:the Social Structure of Competition (London:Harvard University Press) p53

    [24]

    Li P, Zhang J, Xu X K, Small M 2012 Chin. Phys. Lett. 29 048903

    [25]

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

    [26]

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

    [27]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [28]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [29]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [30]

    Liu Y Y, Slotine J J, Barabasi A L 2012 PloS One 7 e44459

    [31]

    Jia T, Pósfai M 2014 Sci. Rep. 4 5379

    [32]

    Jaccad P 1901 Bull. Torrey Bot. Club 37 547

    [33]

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

    [34]

    Dereich S, Mörters P 2013 Ann. Prob. 41 329

    [35]

    Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122

    [36]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

    [37]

    Blagus N,Šubelj L, Bajec M 2012 Physica A 391 2794

    [38]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [39]

    Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166

    [40]

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

    [41]

    Von Mering C, Krause R, Snel B, Cornell M, Oliver S G, Fields S, Bork P 2002 Nature 417 399

    [42]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [43]

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

    [44]

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

    [45]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

  • [1]

    Barabási A L, Albert R 1999 Science 286 509

    [2]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [3]

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

    [4]

    Rogers T 2015 Europhys. Lett. 109 28005

    [5]

    Kinney R, Crucitti P, Albert R, Latora V 2005 Eur. Phys. J. B 46 101

    [6]

    Wang G Z, Cao Y J, Bao Z J, Han Z X 2009 Acta Phys. Sin. 58 3597 (in Chinese)[王光增, 曹一家, 包哲静, 韩祯祥2009物理学报58 3597]

    [7]

    Albert R, Jeong H, Barabási A L 1999 Nature 401 130

    [8]

    Sabidussi G 1966 Psychometrika 31 581

    [9]

    Freeman L C 1977 Sociometry 40 35

    [10]

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

    [11]

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

    [12]

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

    [13]

    L L Y, Zhang Y C, Yeung C H, Zhou T 2011 PloS One 6 e21202

    [14]

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

    [15]

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

    [16]

    Wang J W, Rong L L, Guo T Z 2010 J. Dalian Univ. Technol. 50 822 (in Chinese)[王建伟, 荣莉莉, 郭天柱2010大连理工大学学报50 822]

    [17]

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

    [18]

    Ugander J, Backstrom L, Marlow C, Kleinberg J 2012 Proc. Natl. Acad. Sci. 109 5962

    [19]

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

    [20]

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

    [21]

    Chen D B, Xiao R, Zeng A, Zhang Y C 2014 Europhys. Lett. 104 68006

    [22]

    Ruan Y R, Lao S Y, Xiao Y D, Wang J D, Bai L 2016 Chin. Phys. Lett. 33 028901

    [23]

    Burt R S 2009 Structure Holes:the Social Structure of Competition (London:Harvard University Press) p53

    [24]

    Li P, Zhang J, Xu X K, Small M 2012 Chin. Phys. Lett. 29 048903

    [25]

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

    [26]

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

    [27]

    Liu Y Y, Slotine J J, Barabási A L 2011 Nature 473 167

    [28]

    Orouskhani Y, Jalili M, Yu X H 2016 Sci. Rep. 6 24252

    [29]

    Zhou M Y, Zhuo Z, Liao H, Fu Z Q, Cai S M 2015 Sci. Rep. 5 17459

    [30]

    Liu Y Y, Slotine J J, Barabasi A L 2012 PloS One 7 e44459

    [31]

    Jia T, Pósfai M 2014 Sci. Rep. 4 5379

    [32]

    Jaccad P 1901 Bull. Torrey Bot. Club 37 547

    [33]

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

    [34]

    Dereich S, Mörters P 2013 Ann. Prob. 41 329

    [35]

    Vragovic I, Louis E, Diaz-Guilera A 2005 Phys. Rev. E 71 036122

    [36]

    Latora V, Marchiori M 2007 New J. Phys. 9 188

    [37]

    Blagus N,Šubelj L, Bajec M 2012 Physica A 391 2794

    [38]

    Batagelj V, Mrvar A 1998 Connections 21 47

    [39]

    Isella L, Stehlé J, Barrat A, Cattuto C, Pinton J F 2011 J. Theor. Biol. 271 166

    [40]

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

    [41]

    Von Mering C, Krause R, Snel B, Cornell M, Oliver S G, Fields S, Bork P 2002 Nature 417 399

    [42]

    Watts D J, Strogatz S H 1998 Nature 393 440

    [43]

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

    [44]

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

    [45]

    Buldyrev S V, Parshani R, Paul G, Stanley H E, Havlin S 2010 Nature 464 1025

  • [1] Yang Wu-Hua, Wang Cai-Lin, Zhang Ru-Liang, Zhang Chao, Su Le. Study on avalanche ruggedness of high voltage IGBTs. Acta Physica Sinica, 2023, 72(7): 078501. doi: 10.7498/aps.72.20222248
    [2] Wang Ting-Ting, Liang Zong-Wen, Zhang Ruo-Xi. Importance evaluation method of complex network nodes based on information entropy and iteration factor. Acta Physica Sinica, 2023, 72(4): 048901. doi: 10.7498/aps.72.20221878
    [3] Zhao Hao, Feng Jin-Xia, Sun Jing-Ke, Li Yuan-Ji, Zhang Kuan-Shou. Entanglement robustness of continuous variable Einstein-Podolsky-Rosen-entangled state distributed over optical fiber channel. Acta Physica Sinica, 2022, 71(9): 094202. doi: 10.7498/aps.71.20212380
    [4] 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
    [5] Yang Song-Qing, Jiang Yuan, Tong Tian-Chi, Yan Yu-Wei, Gan Ge-Sheng. A method of evaluating importance of nodes in complex network based on Tsallis entropy. Acta Physica Sinica, 2021, 70(21): 216401. doi: 10.7498/aps.70.20210979
    [6] Huang Li-Ya, Tang Ping-Chuan, Huo You-Liang, Zheng Yi, Cheng Xie-Feng. Node importance based on the weighted K-order propagation number algorithm. Acta Physica Sinica, 2019, 68(12): 128901. doi: 10.7498/aps.68.20190087
    [7] 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
    [8] 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
    [9] Wang Yu, Guo Jin-Li. Evaluation method of node importance in directed-weighted complex network based on multiple influence matrix. Acta Physica Sinica, 2017, 66(5): 050201. doi: 10.7498/aps.66.050201
    [10] Hou Lü-Lin, Lao Song-Yang, Xiao Yan-Dong, Bai Liang. Recent progress in controllability of complex network. Acta Physica Sinica, 2015, 64(18): 188901. doi: 10.7498/aps.64.188901
    [11] Chen Shi-Ming, Lü Hui, Xu Qing-Gang, Xu Yun-Fei, Lai Qiang. The model of interdependent network based on positive/negativecorrelation of the degree and its robustness study. Acta Physica Sinica, 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
    [12] Duan Dong-Li, Wu Xiao-Yue. Cascading failure of scale-free networks based on a tunable load redistribution model. Acta Physica Sinica, 2014, 63(3): 030501. doi: 10.7498/aps.63.030501
    [13] Chen Shi-Ming, Zou Xiao-Qun, Lü Hui, Xu Qing-Gang. Research on robustness of interdependent network for suppressing cascading failure. Acta Physica Sinica, 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
    [14] 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
    [15] 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
    [16] Ren Zhuo-Ming, Shao Feng, Liu Jian-Guo, Guo Qiang, Wang Bing-Hong. Node importance measurement based on the degree and clustering coefficient information. Acta Physica Sinica, 2013, 62(12): 128901. doi: 10.7498/aps.62.128901
    [17] Gao Xiang-Yun, An Hai-Zhong, Fang Wei. Research on fluctuation of bivariate correlation of time series based on complex networks theory. Acta Physica Sinica, 2012, 61(9): 098902. doi: 10.7498/aps.61.098902
    [18] 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
    [19] 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
    [20] Zeng Gao-Rong, Qiu Zheng-Ding. Evaluation model for robustness of digital watermarking. Acta Physica Sinica, 2010, 59(8): 5870-5879. doi: 10.7498/aps.59.5870
Metrics
  • Abstract views:  9258
  • PDF Downloads:  820
  • Cited By: 0
Publishing process
  • Received Date:  20 September 2016
  • Accepted Date:  14 October 2016
  • Published Online:  05 February 2017

/

返回文章
返回