基于改进的局部结构熵复杂网络重要节点挖掘

doi:10.11772/j.issn.1001-9081.2022040562

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (4): 1109-1114.DOI: 10.11772/j.issn.1001-9081.2022040562

基于改进的局部结构熵复杂网络重要节点挖掘

李鹏¹^,², 王世林¹^,²(), 陈光武¹^,², 闫光辉³

^1.兰州交通大学自动化与电气工程学院, 兰州 730070
^2.甘肃省高原交通信息工程及控制重点实验室(兰州交通大学), 兰州 730070
^3.兰州交通大学电子与信息工程学院, 兰州 730070

收稿日期:2022-04-24 修回日期:2022-08-20 接受日期:2022-08-30 发布日期:2022-10-14 出版日期:2023-04-10
通讯作者: 王世林
作者简介:李鹏（1985—），男，青海海东人，博士研究生，CCF会员，主要研究方向：复杂网络、智能交通、信息系统工程；
陈光武（1976—），男，新疆阿克苏人，教授，博士，CCF会员，主要研究方向：交通信息工程及控制、智能感知、自主控制；
闫光辉（1970—），男，河南商丘人，教授，博士，CCF会员，主要研究方向：数据挖掘、社交网络分析。
基金资助:
国家自然科学基金资助项目(62062049);甘肃省科技重大专项(21ZD4WA018);甘肃省科技引导计划项目(2020?61?14);甘肃省自然科学基金资助项目(20JR5RA390)

Key node mining in complex network based on improved local structural entropy

Peng LI¹^,², Shilin WANG¹^,²(), Guangwu CHEN¹^,², Guanghui YAN³

^1.School of Automation and Electrical Engineering，Lanzhou Jiaotong University，Lanzhou Gansu 730070，China
^2.Key Laboratory of Plateau Traffic Information Engineering and Control of Gansu Province （Lanzhou Jiaotong University），Lanzhou Gansu 730070，China
^3.School of Electronic and Information Engineering，Lanzhou Jiaotong University，Lanzhou Gansu 730070，China

Received:2022-04-24 Revised:2022-08-20 Accepted:2022-08-30 Online:2022-10-14 Published:2023-04-10
Contact: Shilin WANG
About author:LI Peng， born in 1985， Ph. D. candidate. His research interests include complex networks， intelligent transportation， information system engineering.
CHEN Guangwu， born in 1976， Ph. D.， professor. His research interests include traffic information engineering and control， intelligent perception， autonomous control.
YAN Guanghui， born in 1970， Ph. D.， professor. His research interests include data mining， social network analysis.
Supported by:
National Natural Science Foundation of China(62062049);Gansu Science and Technology Major Project(21ZD4WA018);Gansu Province Science and Technology Guidance Plan(2020-61-14);Natural Science Foundation of Gansu Province(20JR5RA390)

摘要/Abstract

摘要：

识别复杂网络中的关键节点对优化网络结构以及信息的有效传播起着至关重要的作用。局部结构熵（LE）利用局部网络对整个网络的影响代替节点对整个网络的影响以识别重要节点，然而LE未考虑高聚集性网络和节点与邻居节点形成环的情况，存在一定的局限性。针对以上不足，首先，提出了改进LE的节点重要性评价方法PLE（Penalized Local structural Entropy），即在LE的基础上引入集聚系数（CC）作为惩罚项，从而适当惩罚网络中的高聚集性节点；其次，由于PLE的惩罚项对三元闭包结构上的节点惩罚力度过大，又提出了PLE的改进方法PLEA（Penalized Local structural Entropy Advancement），即在惩罚项前引入一个控制系数，以控制惩罚力度。对5个不同规模的真实网络进行选择性攻击实验，实验结果表明，在美国西部各州电网和美国航空网两个网络中，与LE方法相比，PLEA的识别准确率分别提升了26.3%和3.2%；与K-Shell（KS）方法相比，PLEA的识别准确率分别提升了380%和5.43%；与DCL（Degree and Clustering coefficient and Location）方法相比，PLEA的识别准确率分别提升了14.4%和24%。同时，PLEA识别的重要节点对网络造成的破坏更大，验证了引入CC作为惩罚项的合理性，以及PLEA的有效性和优越性。PLEA综合考虑了节点的邻居个数和节点的局部网络结构，计算简单，对于刻画大规模网络的可靠性与抗毁性具有十分重要的意义。

关键词: 复杂网络, 重要节点, 局部结构熵, 惩罚项, 集聚系数

Abstract:

The identification of key nodes in complex network plays an important role in the optimization of network structure and effective propagation of information. Local structural Entropy （LE） can be used to identify key nodes by using the influence of the local network on the whole network instead of the influence of nodes on the whole network. However， the cases of the highly aggregative network and nodes forming a loop with neighbor nodes are not considered in LE， which leads to some limitations. To address these limitations， firstly， an improved LE based node importance evaluation method， namely PLE （Penalized Local structural Entropy）， was proposed， in which based on the LE， the Clustering Coefficient （CC） was introduced as a penalty term to penalize the highly aggregative nodes in the network appropriately. Secondly， due to the fact that the penalty of PLE penalizing the nodes in triadic closure structure is too much， an improved method of PLE， namely PLEA （Penalized Local structural Entropy Advancement） was proposed， in which control coefficient was introduced in front of the penalty term to control the penalty strength. Selective attack experiments on five real networks with different sizes were conducted. Experimental results show that in the western US states grid and the US Airlines， PLEA has the identification accuracy improved by 26.3% and 3.2% compared with LE respectively， by 380% and 5.43% compared with K-Shell （KS） method respectively， and by 14.4% and 24% compared with DCL （Degree and Clustering coefficient and Location） method respectively. The key nodes identified by PLEA can cause more damage to the network， verifying the rationality of introducing the CC as a penalty term， and the effectiveness and superiority of PLEA. The integration of the number of neighbors and the local network structure of nodes with the simplicity of computation makes it more effective in describing the reliability and invulnerability of large-scale networks.

Key words: complex network, key node, Local structural Entropy (LE), penalty term, Clustering Coefficient (CC)

中图分类号:

TP301.6

李鹏, 王世林, 陈光武, 闫光辉. 基于改进的局部结构熵复杂网络重要节点挖掘[J]. 计算机应用, 2023, 43(4): 1109-1114.

Peng LI, Shilin WANG, Guangwu CHEN, Guanghui YAN. Key node mining in complex network based on improved local structural entropy[J]. Journal of Computer Applications, 2023, 43(4): 1109-1114.

图/表 10

图 1 局部网络示意图

Fig. 1 Schematic diagram of local networks

表 1 利用式（5）对图1（a）中各节点进行重要性度量

Tab. 1 Importance measure for each node in Fig.1（a） by using Eq.（5）

节点	$V P L E$	节点	$V P L E$
1	0.04	6	0.50
2	0.04	7	1.43
3	0.50	8	0.50
4	1.35	9	0.50
5	1.06

表 1 利用式（5）对图1（a）中各节点进行重要性度量

Tab. 1 Importance measure for each node in Fig.1（a） by using Eq.（5）

节点	$V P L E$	节点	$V P L E$
1	0.04	6	0.50
2	0.04	7	1.43
3	0.50	8	0.50
4	1.35	9	0.50
5	1.06

表 2 利用式（7）对图1（a）各节点进行重要性度量

Tab. 2 Importance measure for each node in Fig. 1（a） by using Eq.（7）

节点	$V P L E A$	节点	$V P L E A$
1	0.54	6	0.50
2	0.54	7	1.43
3	0.50	8	0.50
4	1.35	9	0.50
5	1.06

表 2 利用式（7）对图1（a）各节点进行重要性度量

Tab. 2 Importance measure for each node in Fig. 1（a） by using Eq.（7）

节点	$V P L E A$	节点	$V P L E A$
1	0.54	6	0.50
2	0.54	7	1.43
3	0.50	8	0.50
4	1.35	9	0.50
5	1.06

图 2 基于PLEA的重要节点识别流程

Fig. 2 Flow of PLEA based key node identification

表 3 各真实网络的统计特性

Tab. 3 Statistical characteristics of each real network

网络	节点数量	边数量	平均度	平均距离	平均聚集系数
Football	115	613	10.661	2.508	0.403
Dolphins	62	159	5.129	3.357	0.259
Email	1 133	5 452	9.624	3.606	0.625
US Airlines	332	2 126	12.807	2.738	0.625
western US states grid	4 941	6 954	2.669	18.989	0.080

图 3 Dolphins网络和Football网络删除不同比例节点时e值的变化

Fig. 3 Changes of e value in Dolphins network and Football network when nodes with different proportions are deleted

表 4 Dolphins网络在不同度量方法下排名前10的节点

Tab. 4 Top 10 nodes in Dolphins network under different measurement methods

方法	排名前10的节点序号
方法	1	2	3	4	5	6	7	8	9	10
PLEA	14	37	20	45	1	33	51	29	36	17
LE	14	45	37	33	20	51	29	57	1	13
DC	6	9	13	18	29	45	51	57	30	7
KS	14	37	45	33	51	17	20	29	51	1
DCL	36	20	14	37	1	51	17	23	25	29
CEN	36	20	37	14	1	17	45	51	40	50

表 5 Football网络在不同度量方法下排名前10的节点

Tab. 5 Top 10 nodes in Football network under different measurement methods

方法	排名前10的节点序号
方法	1	2	3	4	5	6	7	8	9	10
PLEA	82	80	58	69	6	3	15	0	104	5
LE	7	15	53	2	67	88	104	1	3	6
DC	46	49	67	73	83	110	74	111	60	6
KS	0	1	2	3	5	6	7	15	53	67
DCL	58	82	80	63	36	42	69	24	6	43
CEN	82	58	80	69	63	24	6	0	15	36

图 4 Email网络、美国航空网以及美国西部各州电网删除不同比例节点时e的变化

Fig. 4 Changes of e in Email network， US Airlines and western US states grid network when nodes with different proportions are deleted

表 6 美国西部各州电网在不同度量方法下排名前10的节点

Tab. 6 Top 10 nodes in western US states power under different measurement methods

方法	排名前10的节点序号
方法	1	2	3	4	5	6	7	8	9	10
PLEA	2553	4458	3895	4345	2382	2542	2434	3468	1334	2617
LE	2553	4458	4345	3895	2542	4352	4384	4381	2585	4332
KS	4398	4332	4352	4335	4344	4347	4381	4384	4401	4402
DC	2553	4458	831	3468	4345	2382	2542	2575	2585	3895
DCL	4458	3468	2575	831	2439	2382	2553	1224	2554	1334
CEN	4458	3468	2553	831	2575	2382	2439	1224	2434	1005

参考文献 25

1	XU X， ZHU C， WANG Q Y， et al. Identifying vital nodes in complex networks by adjacency information entropy［J］. Scientific Reports， 2020， 10： No.2691. 10.1038/s41598-020-59616-w
2	任晓龙，吕琳媛. 网络重要节点排序方法综述［J］. 科学通报， 2014， 59（13）： 1175-1197. 10.1360/972013-1280
	REN X L， LYU L Y. Review of ranking nodes in complex networks［J］. Chinese Science Bulletin， 2014， 59（13）：1175-1197. 10.1360/972013-1280
3	任卓明，刘建国，邵凤，等. 复杂网络中最小K-核节点的传播能力分析［J］. 物理学报， 2013， 62（10）： No.108902. 10.7498/aps.62.108902
	REN Z M， LIU J G， SHAO F， et al. Analysis of the spreading influence of the nodes with minimum K-shell value in complex networks［J］. Acta Physica Sinica. 2013， 62（10）： No.108902. 10.7498/aps.62.108902
4	YANG X， XIAO F Y. An improved gravity model to identify influential nodes in complex networks based on k-shell method［J］. Knowledge-Based Systems， 2021， 227： No.107198. 10.1016/j.knosys.2021.107198
5	SHANG Q Y， DENG Y， CHEONG K H. Identifying influential nodes in complex networks： effective distance gravity model［J］. Information Sciences， 2021， 577：162-179. 10.1016/j.ins.2021.01.053
6	ULLAH A， WANG B， SHENG J F， et al. Identifying vital nodes from local and global perspectives in complex networks［J］. Expert Systems with Applications， 2021， 186： No.115778. 10.1016/j.eswa.2021.115778
7	郭庆来，辛蜀骏，王剑辉，等. 由乌克兰停电事件看信息能源系统综合安全评估［J］. 电力系统自动化， 2016， 40（5）： 145-147. 10.7500/AEPS20160113101
	GUO Q L， XIN S J， WANG J H， et al. Comprehensive security assessment for a cyber physical energy system： a lesson from Ukraine’s blackout［J］. Automation of Electric Power Systems， 2016， 40（5）：145-147. 10.7500/AEPS20160113101
8	胡钢，徐翔，高浩，等. 基于邻接信息熵的网络节点重要性识别算法［J］. 系统工程理论与实践， 2020， 40（3）： 714-725. 10.12011/1000-6788-2018-1805-12
	HU G， XU X， GAO H， et al. Node importance recognition algorithm based on adjacency information entropy in networks［J］. Systems Engineering — Theory & Practice， 2020， 40（3）：714-725. 10.12011/1000-6788-2018-1805-12
9	ALBERT R， JEONG W， BARABÁSI A L. Diameter of the world-wide web［J］. Nature， 1999， 401（6749）： 130-131. 10.1038/43601
10	BRANDES U， BORGATTI S P， FREEMAN L C. Maintaining the duality of closeness and betweenness centrality［J］. Social Networks， 2016， 44：153-159. 10.1016/j.socnet.2015.08.003
11	FREEMAN L C. A set of measures of centrality based on betweenness［J］. Sociometry， 1977， 40（1）： 35-41. 10.2307/3033543
12	NEWMAN M E J. Finding community structure in networks using the eigenvectors of matrices［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2006， 74（3）： No.036104. 10.1103/physreve.74.036104
13	BERAHMAND K， BOUYER A， SAMADI N. A new local and multidimensional ranking measure to detect spreaders in social networks［J］. Computing， 2019， 101（11）： 1711-1733. 10.1007/s00607-018-0684-8
14	BERAHMAND K， BOUYER A， SAMADI N. A new centrality measure based on the negative and positive effects of clustering coefficient for identifying influential spreaders in complex networks［J］. Chaos， Solitons and Fractals， 2018， 110： 41-54. 10.1016/j.chaos.2018.03.014
15	马润年，王班，王刚，等. 基于互信息的通信网络节点重要性度量方法［J］. 电子学报， 2017， 45（3）： 747-752. 10.3969/j.issn.0372-2112.2017.03.035
	MA R N， WANG B， WANG G， et al. Evaluation method for node importance in communication network based on mutual information［J］. Acta Electronica Sinica， 2017， 45（3）：747-752. 10.3969/j.issn.0372-2112.2017.03.035
16	FEI L G， DENG Y. A new method to identify influential nodes based on relative entropy［J］. Chaos， Solitons and Fractals， 2017， 104：257-267. 10.1016/j.chaos.2017.08.010
17	ZHANG Q， LI M Z， DU Y X， et al. Local structure entropy of complex networks［EB/OL］. （2014-12-12）［2022-02-11］..
18	吕非非，徐雅斌，李卓，等. 面向微博影响力的社交网络特征分析［J］. 计算机应用， 2013， 33（12）：3359-3362， 3418. 10.3724/sp.j.1087.2013.03359
	LYU F F， XU Y B， LI Z， et al. Analysis of characteristics of social networks in terms of microblog impact［J］. Journal of Computer Applications， 2013， 33（12）： 3359-3362， 3418. 10.3724/sp.j.1087.2013.03359
19	GIRVAN M， NEWMAN M E J. Community structure in social and biological networks［J］. Proceedings of the National Academy of Sciences of the United States of America， 2002， 99（12）： 7821-7826. 10.1073/pnas.122653799
20	LUSSEAU D， SCHNEIDER K， BOISSEAU O J， et al. The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations［J］. Behavioral Ecology and Sociobiology， 2003， 54（4）：396-405. 10.1007/s00265-003-0651-y
21	GUIMERÀ R， DANON L， DÍAZ-GUILERA A， et al. Self-similar community structure in a network of human interactions［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2003， 68（6）： No.065103. 10.1103/physreve.68.065103
22	WATTS D J， STROGATZ S H. Collective dynamics of ‘small-world’ networks［J］. Nature， 1998， 393（6684）： 440-442. 10.1038/30918
23	NEMESURE M D， SCHWEDHELM T M， SACERDOTE S， et al. A measure of local unique-ness to identify linchpins in a social network with node attributes［J］. Applied Network Science， 2021， 6： No.56. 10.1007/s41109-021-00400-8
24	VRAGOVIĆ I， LOUIS E， DÍAZ-GUILERA A. Efficiency of informational transfer in regular and complex networks［J］. Physical Review. E， Statistical， Nonlinear， and Soft Matter Physics， 2005， 71（3）： No.036122. 10.1103/physreve.71.036122
25	任卓明，邵凤，刘建国，等. 基于度与集聚系数的网络节点重要性度量方法研究［J］. 物理学报， 2013， 62（12）： No.128901. 10.7498/aps.62.128901
	REN Z M， SHAO F， LIU J G， et al. Node importance measurement based on the degree and clustering coefficient information［J］. Acta Physica Sinica， 2013， 62（12）：No.128901. 10.7498/aps.62.128901

[1]	李占利, 李颖, 罗香玉, 罗颖骁. 基于Monte-Carlo迭代求解策略的局部社区发现算法[J]. 《计算机应用》唯一官方网站, 2023, 43(1): 104-110.
[2]	孟昱煜, 郭静. 信息熵改进主成分分析模型的链路预测算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2823-2829.
[3]	郝志刚, 秦丽. 基于多属性综合评价的食品安全标准引用网络重要节点发现方法[J]. 《计算机应用》唯一官方网站, 2022, 42(4): 1178-1185.
[4]	胡军, 许正康, 刘立, 钟福金. 融合多粒度社区信息的网络嵌入方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 663-670.
[5]	陈广福, 王海波, 连雁平. 基于高阶自包含协同过滤的有向网络链路预测[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3060-3068.
[6]	蔡彪, 李蕊岑, 吴媛媛. 相似性特征对链路预测的影响与增强[J]. 计算机应用, 2021, 41(9): 2569-2577.
[7]	李亚芳, 梁烨, 冯韦玮, 祖宝开, 康玉健. 基于社区优化的深度网络嵌入方法[J]. 计算机应用, 2021, 41(7): 1956-1963.
[8]	李萍, 汪芬, 陈祺东, 孙俊. 求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J]. 计算机应用, 2021, 41(3): 803-811.
[9]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.
[10]	成其伟, 陈启买, 贺超波, 刘海. 基于改进对称二值非负矩阵分解的重叠社区发现方法[J]. 计算机应用, 2020, 40(11): 3203-3210.
[11]	刘昱阳, 李龙杰, 单娜, 陈晓云. 融合聚集系数的链接预测方法[J]. 计算机应用, 2020, 40(1): 28-35.
[12]	邵豪, 王伦文, 邓健. 基于H运算的动态网络重要节点识别方法[J]. 计算机应用, 2019, 39(9): 2669-2674.
[13]	王西龙, 王继成, 罗成, 田秀霞. 时间尺度与选择倾向性协同作用下的演化博弈模型[J]. 计算机应用, 2019, 39(6): 1824-1828.
[14]	张希, 朱利, 刘路辉, 詹杭龙, 卢艳民. 基于多层网络的银行间市场信用拆借智能风险传染机制[J]. 计算机应用, 2019, 39(5): 1507-1511.
[15]	刘正铭, 马宏, 刘树新, 李海涛, 常圣. 融合节点描述属性信息的网络表示学习算法[J]. 计算机应用, 2019, 39(4): 1012-1020.

基于改进的局部结构熵复杂网络重要节点挖掘

Key node mining in complex network based on improved local structural entropy

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 10

参考文献 25

相关文章 15

编辑推荐

Metrics