-
节点重要性度量对于研究复杂网络鲁棒性与脆弱性具有重要意义.大规模实际复杂网络的结构往往随着时间不断变化，在获取网络全局信息用于评估节点重要性方面具有局限性.通过量化节点局部网络拓扑的重合程度来定义节点间的相似性，提出了一种考虑节点度以及邻居节点拓扑重合度的节点重要性评估算法，算法只需要获取节点两跳内的邻居节点信息，通过计算邻居节点对之间的相似度，便可表征其在复杂网络中的结构重要性.基于六个经典的实际网络和一个人工的小世界网络，分别以静态与动态的方式对网络进行攻击，通过对极大连通系数与网络效率两种评估指标的实验结果对比，证明了所提算法优于基于局域信息的度指标、半局部度指标、基于节点度及其邻居度的WL指标以及基于节点位置的K-shell指标.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
计量
- 文章访问数: 11888
- PDF下载量: 863
- 被引次数: 0
下载:
