-
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.
-
Keywords:
- complex network /
- robustness /
- node importance /
- neighborhood similarity
[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
Catalog
Metrics
- Abstract views: 12026
- PDF Downloads: 864
- Cited By: 0
下载:
