Centrality algorithm of complex network based on neighborhood betweenness entropy and neighborhood degree entropy

Abstract

Abstract: Identifying the important nodes of complex network is always the key point of complex network research, and also the important theoretical basis of network stability determination. The commonly used central indicators to identify the important nodes include the centrality of the betweenness, the centrality of the degree, the centrality of the eigenvector and the centrality of K-core. These indicators have some limitations in identifying the important nodes. In order to solve the above problems, the neighbor node set is divided into two parts: the related neighbor node set (M_R) and the unrelated neighbor node set (M_UR). Based on the characteristics of graph entropy, a new information entropy NBE and NDE are proposed. Combined with NBE and NDE, new centrality RNC and URNC are proposed. In the experiment, dynamic attack is used to evaluate the efficiency of the new centrality index on one experimental network model and five real networks. By comparison, the new centrality is more efficient than the traditional centrality in identifying important nodes.

Key words: complex network, unrelated neighbor centrality (URNC), related neighbor centrality (RNC)

CLC Number:

TP393

LU Peng-li, ZHOU Geng. Centrality algorithm of complex network based on neighborhood betweenness entropy and neighborhood degree entropy[J]. Journal of Lanzhou University of Technology, 2021, 47(4): 91-98.

References

[1] ZANIN M,LILLO F.Modelling the air transport with complex networks:a short review [J].The European Physical Journal Special Topics,2013,215(1):5-21.
[2] YANG Y,NISHIKAWA T,MOTTER A E.Small vulnerable sets determine large network cascades in power grids [J]. Science,2017,358(6365):886-892.
[3] ARULARASAN A N,SURESH A,SEERANGAN K.Identification and classification of best spreader in the domain of interest over the social networks [J].Cluster Computing,2019,22:4035-4045.
[4] SHANG Y L.Degree distribution dynamics for disease spreading with individual awareness [J].Journal of Systems Science and Complexity,2015,28(1):96-104.
[5] BELLINGERI M,BODINI A.Food web’s backbones and energy delivery in ecosystems [J].Oikos,2016,125(4):586-594.
[6] MCDONALD-MADDEN E,SABBADIN R,GAME E T.Using food-web theory to conserve ecosystems [J].Nature Communications,2016,7:10245.
[7] BARABACUTESI A L,ALBERT R.Emergence of scaling in random networks [J].Science,2009,325(5939):412-413.
[8] WATTS D J,STROGATZ S H.Collective dynamics of small world networks [J].Nature,1998,393(6684):440-442.
[9] XU B,WANG F,CHEN D.Hamiltonian modeling of multi-hydro-turbine governing systems with sharing common penst-ock and dynamic analyses under shock load [J].Energy Conversion and Management,2016,108:478-487.
[10] BARABASI A L,GULBAHCE N,LOSCALZO J.Network medicine: a network-based approach to human disease [J].Nature Reviews Genetics,2011,12(1):56-68.
[11] XIONG X,HU Y.Research on the dynamic of opinion spread based on social network services [J].Acta Physical Sinica,2012,61(15):104-110.
[12] ALBERT R,ALBERT I,NAKARADO G L.Structural vulnerability of the North American power grid [J].Physical Review E,2004,69(2):025103.
[13] 于会,刘尊,李勇军.基于多属性决策的复杂网络节点重要性综合评价方法 [J].物理学报,2013,62(2):46-54.
[14] BONACICH P F.Factoring and weighting approaches to status scores and clique identification [J].Journal of Mathematical Biology,1972,2(1):113-120.
[15] FREEMAN L C. Centrality in social networks conceptual clarification [J].Social Networks,1978,1(3):215-239.
[16] NEWMAN M E J.A measure of betweenness centrality based on random walks [J].Social Networks,2005,27(1):39-54.
[17] STEPHENSON K,ZELEN M.Rethinking centrality:methods and examples [J].Social Networks,1989,14(1):1-37.
[18] ESTRADA E,RODRÍGUEZ-VELÁZQUEZ J A.Subgraph centrality in complex networks [J].Physical Review E,2005,71(5):056103.
[19] FU L D,GAO L,MA X K.A centrality measure based on spectral optimization of modularity density [J].Science China:Information Science,2010,53:1727-1737.
[20] FREEMAN L C. A set of measures of centrality based on betweenness [J].Sociometry,1997,40(1):35-41.
[21] SHAN L,YI Y,ZHANG Z.Improving information centrality of a node in complex networks by adding edges [C]//Proceedings of Twenty-Seventh International Joint Conference on Artificial Intelligence.Stockholm:[s.n.],2018:3535-3541.
[22] FENG Xiangnan,WEI Wei,WANG Jiannan.Research on centralities based on von Neumann entropy for nodes and motifs [J/OL].[2020-01-15].https://arxiv.org/pdf/1707.00386.pdf.
[23] MASSIMO S,MANLIO D D.Distance entropy cartography characterises centrality in complex networks [J].Entropy,2018,20(4):268-280.
[24] NIE T Y,GUO Z,ZHAO K,et al.Using mapping entropy to identify node centrality in complex networks [J].Physic A,2016,453:290-297.
[25] 卢鹏丽,郭旭东,董璊,等.基于介度熵的复杂网络节点重要度识别方法 [J].兰州理工大学学报,2020,46(2):111-115.
[26] Pajek datasets [DB/OL].(2003-10-11)[2018-09-15].http://vlado.fmf.uni-lj.si/pub/networks/data/.
[27] 谭跃进,吴俊,邓宏钟.复杂网络中节点重要度评估的节点收缩方法 [J].系统工程理论与实践,2013,62(2):46-54.
[28] HAGE P,HARARY F.Eccentricity and centrality in networks [J].Social Networks,1995,17(1):57-63.