基于邻介熵和邻度熵的复杂网络中心性算法

兰州理工大学学报 ›› 2021, Vol. 47 ›› Issue (4): 91-98.

• 自动化技术与计算机技术 • 上一篇下一篇

基于邻介熵和邻度熵的复杂网络中心性算法

卢鹏丽^*, 周庚

兰州理工大学计算机与通信学院, 甘肃兰州 730050

收稿日期:2020-03-02 出版日期:2021-08-01 发布日期:2021-09-07
通讯作者: 卢鹏丽(1973-),女,甘肃酒泉人,博士,教授,博导.Email:lupengli88@163.com
基金资助:
国家自然科学基金(11361033),甘肃省自然科学基金(1212RJZA029)

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

LU Peng-li, ZHOU Geng

College of Computer and Communication, Lanzhou Univ. of Tech., Lanzhou 730050, China

Received:2020-03-02 Online:2021-08-01 Published:2021-09-07

摘要/Abstract

摘要： 识别复杂网络的重要节点是复杂网络研究的关键点,也是网络稳定性判定的重要理论基础.常用的识别节点影响力的中心性指标有介数中心性、度中心性、特征向量中心性和K-core 中心性等,这些指标在识别重要节点时存在一定的局限性.为了解决以上问题,将节点v_i的邻居节点集划分成关联邻居节点集(MR)和非关联邻居节点集(M_UR),结合图的信息熵以及节点的介数中心性和度中心性,提出新的中心性指标,即基于邻介熵(NBE)和邻度熵(NDE)的关联邻居中心性RNC 和非关联邻居中心性URNC.实验通过动态攻击来评估新的中心性指标在一个实验网络模型和五个真实网络上的效率,结果表明,新的中心性比传统的中心性具有更高的识别重要节点的效率.

关键词: 复杂网络, 非关联邻居中心性(URNC), 关联邻居中心性(RNC)

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)

中图分类号:

TP393

卢鹏丽, 周庚. 基于邻介熵和邻度熵的复杂网络中心性算法[J]. 兰州理工大学学报, 2021, 47(4): 91-98.

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.

参考文献

[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.

基于邻介熵和邻度熵的复杂网络中心性算法

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

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	苏建宁, 白睿昇, 李雄, 白兴易. 基于约束网络的产品进化设计[J]. 兰州理工大学学报, 2021, 47(4): 59-65.
[2]	祝延波. 基于图论的中国高铁网节点中心性进化研究[J]. 兰州理工大学学报, 2021, 47(3): 97-104.
[3]	卢鹏丽, 周庚. 基于网络局部和全局特性的组合中心性度量措施[J]. 兰州理工大学学报, 2021, 47(1): 91-96.
[4]	卢鹏丽, 于洲. 基于度与H指数扩展的复杂网络节点排序方法[J]. 兰州理工大学学报, 2020, 46(5): 100-106.
[5]	卢鹏丽, 郭旭东, 董璊, 曹乐. 基于介度熵的复杂网络节点重要度识别方法[J]. 兰州理工大学学报, 2020, 46(2): 111-115.