基于全局—局部属性的复杂网络节点综合影响力评估算法

doi:10.11959/j.issn.2096-3750.2022.00282

物联网学报 ›› 2022, Vol. 6 ›› Issue (3): 133-145.doi: 10.11959/j.issn.2096-3750.2022.00282

基于全局—局部属性的复杂网络节点综合影响力评估算法

蒋伟进¹^,², 杨莹¹^,², 罗田甜¹^,², 周文颖¹^,², 李恩¹^,², 张小威¹^,²

¹ 湖南工商大学计算机学院，湖南长沙 410205
² 数据智能与智慧社会国家重点实验室（培育）基地，湖南长沙 410205
³ 湖南工商大学前沿交叉学院，湖南长沙 410205

修回日期:2022-07-03 出版日期:2022-08-05 发布日期:2022-08-08
作者简介:蒋伟进（1964- ），男，博士，湖南工商大学计算机学院二级教授，主要研究方向为网络安全、社会计算、区块链技术和群体智能感知
杨莹（1999- ），女，湖南工商大学计算机学院硕士生，主要研究方向为复杂网络、网络安全和区块链技术
罗田甜（1998- ），女，湖南工商大学前沿交叉学院硕士生，主要研究方向为网络安全、区块链技术和社会计算
周文颖（1999- ），女，湖南工商大学计算机学院硕士生，主要研究方向为网络安全、区块链技术和社会计算
李恩（1995- ），男，湖南工商大学计算机学院硕士生，主要研究方向为网络安全和区块链技术
张小威（1999- ），男，湖南工商大学计算机学院硕士生，主要研究方向为网络安全、社会计算和社交网络
基金资助:
国家自然科学基金资助项目(61772196);湖南省自然科学基金资助项目(2020JJ4249);湖南省教育厅科学研究重点项目(21A0374);湖南省研究生科研创新项目(CX20211108);湖南省研究生科研创新项目(CX20211151)

Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes

Weijin JIANG¹^,², Ying YANG¹^,², Tiantian LUO¹^,², Wenying ZHOU¹^,², En LI¹^,², Xiaowei ZHANG¹^,²

¹ School of Computer Science, Hunan University of Technology and Business, Changsha 410205, China
² State Key Laboratory of Digital Intelligence and Smart Society (Cultivating) Base, Changsha 410205, China
³ School of Advanced Interdisciplinary Studies, Hunan University of Technology and Business, Changsha 410205, China

Revised:2022-07-03 Online:2022-08-05 Published:2022-08-08
Supported by:
The National Natural Science Foundation of China(61772196);The Natural Science Foundation of Hunan Province(2020JJ4249);The Key Scientific Research Project of Hunan Provincial Department of Education(21A0374);The Hunan Provincial Innovation Foundation for Postgraduate(CX20211108);The Hunan Provincial Innovation Foundation for Postgraduate(CX20211151)

摘要/Abstract

摘要：

挖掘网络中的关键节点在信息传播、病毒营销、舆论控制等的演进过程中发挥着巨大的作用，关键节点的识别可以有效地帮助控制网络攻击、检测金融风险、抑制病毒和谣言的传播、防止恐怖袭击等。为了突破现有节点影响力评估方法存在的算法复杂度高、准确度低以及评价指标内在作用机制评估角度片面的限制，提出了一种识别关键节点的综合影响力（CI, comprehensive influence）评估算法。该算法通过同时处理网络的局部和全局拓扑来对节点重要性进行排序，从多个角度整合网络属性信息，提供更全面的节点重要性度量。算法中的全局属性考虑的是邻居节点以及节点之间的最短距离，节点的信息熵用来表示节点的局部属性，通过一个参数来调整全局和局部属性的权重比。使用SIR（susceptible infected recovered）模型和Kendall相关系数作为评价标准，在不同规模的现实世界网络上进行实验分析，结果表明，所提出的方法能在识别关键节点方面优于介数中心性（BC, betweenness centrality）、接近中心性（CC, closeness centrality）、重力指数中心性（GIC, gravity index centrality）、全局结构模型（GSM, global structure model）等著名的启发式算法，并且具有更好的排序单调性、更稳定的度量结果，对网络拓扑的适应性更强，适用于绝大多数具有不同结构的真实网络。

关键词: 关键节点, 复杂网络, 节点信息熵, 多属性综合评估

Abstract:

Mining key nodes in the network plays a great role in the evolution of information dissemination, virus marketing, and public opinion control, etc.The identification of key nodes can effectively help to control network attacks, detect financial risks, suppress the spread of viruses diseases and rumors, and prevent terrorist attacks.In order to break through the limitations of existing node influence assessment methods with high algorithmic complexity and low accuracy, as well as one-sided perspective of assessing the intrinsic action mechanism of evaluation metrics, a comprehensive influence (CI) assessment algorithm for identifying critical nodes was proposed, which simultaneously processes the local and global topology of the network to perform node importance.The global attributes in the algorithm consider the information entropy of neighboring nodes and the shortest distance nodes between nodes to represent the local attributes of nodes, and the weight ratio of global and local attributes was adjusted by a parameter.By using the SIR (susceptible infected recovered) model and Kendall correlation coefficient as evaluation criteria, experimental analysis on real-world networks of different scales shows that the proposed method is superior to some well-known heuristic algorithms such as betweenness centrality (BC), closeness centrality (CC), gravity index centrality(GIC), and global structure model (GSM), and has better ranking monotonicity, more stable metric results, more adaptable to network topologies, and is applicable to most of the real networks with different structure of real networks.

Key words: node importance, complex networks, node information entropy, integrated multi-attribute evaluation

中图分类号:

TP301.6

蒋伟进, 杨莹, 罗田甜, 周文颖, 李恩, 张小威. 基于全局—局部属性的复杂网络节点综合影响力评估算法[J]. 物联网学报, 2022, 6(3): 133-145.

Weijin JIANG, Ying YANG, Tiantian LUO, Wenying ZHOU, En LI, Xiaowei ZHANG. Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes[J]. Chinese Journal on Internet of Things, 2022, 6(3): 133-145.

图/表 13

图1

图2

表1

表2

图3

图4

表3

图5

图6

图7

图8

图9

表4

参考文献 39

[1]	LI X X , HU W , SHANG T ,et al. Security analysis of power system network based on complex network[C]// Proceedings of 2020 IEEE 4th Conference on Energy Internet and Energy System Integration. Piscataway,IEEE Press, 2020: 4336-4341.
[2]	KHOSROSERESHKI F , MOAVENI B . Traffic modeling and validation for intersecting metro lines by considering the effect of transfer stations[J]. IEEE Access,, 10: 1946-1955.
[3]	GARCIA J O , ASHOURVAN A , MULDOON S ,et al. Applications of community detection techniques to brain graphs,algorithmic considerations and implications for neural function[J]. Proceedings of the IEEE, 2018,106(5): 846-867.
[4]	ZHAO J Y , MO H M , DENG Y . An efficient network method for time series forecasting based on the DC algorithm and visibility relation[J]. IEEE Access, 8: 7598-7608.
[5]	LI X Y , ZHOU M Y , WU X Y ,et al. A novel method to identify multiple influential nodes in complex networks[J]. Scientia Sinica Informationis, 2019,49(10): 1333-1342.
[6]	LIU X , HE D , LIU C ,et al. Social network information propagation dynamic analysis based on time-varying damping motion[J]. Scientia Sinica Informationis, 2021,51(11): 1867.
[7]	TRONCOSO F , WEBER R . Integrating relations and criminal background to identifying key individuals in crime networks[J]. Decision Support Systems, 2020,139,113405.
[8]	HUANG C S , ZHU L . Robust evaluation method of communication network based on the combination of complex network and big data[J]. Neural Computing and Applications, 2021,33(3): 887-896.
[9]	FAN L J , JIANG Z Y , WANG Q . Robustness evaluation for real traffic network from complex network perspective[J]. International Journal of Modern Physics C, 2021,32(8): 2150102.
[10]	ZHUD R , WANGH F , DUAN J D ,et al. Study of Improved PageRank algorithm in key node identification of power system[C]// Proceedings of 2020 4th International Conference on HVDC (HVDC). Piscataway:IEEE Press, 2020: 1154-1159.
[11]	XU X , ZHU C , WANG Q Y ,et al. Identifying vital nodes in complex networks by adjacency information entropy[J]. Scientific Reports,2020,10, 2691.
[12]	MAJI G , MANDAL S , SEN S . A systematic survey on influential spreaders identification in complex networks with a focus on K-shell based techniques[J]. Expert Systems With Applications, 2020,161:113681.
[13]	MAJI G , NAMTIRTHA A , DUTTA A ,et al. Influential spreaders identification in complex networks with improved K-shell hybrid method[J]. Expert Systems With Applications, 2020,144,113092.
[14]	ZHAO G H , JIA P , ZHOU A M ,et al. InfGCN,identifying influential nodes in complex networks with graph convolutional networks[J]. Neurocomputing, 2020,414: 18-26.
[15]	YANG H H , AN S . Critical nodes identification in complex networks[J]. Symmetry, 2020,12(1): 123.
[16]	GUO C G , YANG L W , CHEN X ,et al. Influential nodes identification in complex networks via information entropy[J]. Entropy (Basel,Switzerland), 2020,22(2): 242.
[17]	MAHARANI W , ADIWIJAYA , GOZALI A A . Degree centrality and eigenvector centrality in twitter[C]// Proceedings of 2014 8th International Conference on Telecommunication Systems Services and Applications (TSSA). Piscataway,IEEE Press, 2014: 1-5.
[18]	LIU X Y , DING N , LIU C ,et al. Novel social network community discovery method combined local distance with node rank optimization function[J]. Applied Intelligence, 2021,51(7): 4788-4805.
[19]	WANG Y F , YAN G H , MA Q Q ,et al. Identifying influential spreaders on weighted networks based on Cluster Rank[C]// Proceedings of 2017 10th International Symposium on Computational Intelligence and Design (ISCID). Piscataway,IEEE Press, 2017: 476-479.
[20]	KITSAK M , GALLOS L K , HAVLIN S ,et al. Identification of influential spreaders in complex networks[J]. Nature Physics, 2010,6(11): 888-893.
[21]	MALANG K , WANG S L , PHAPHUANGWITTAYAKUL A ,et al. Identifying influential nodes of global terrorism network,a comparison for skeleton network extraction[J]. Physica A,Statistical Mechanics and Its Applications, 2020,545,123769.
[22]	OKAMOTO K , CHEN W , LI X Y . Ranking of closeness centrality for large-scale social networks[C]// Frontiers in Algorithmics, 2008: 186-195.
[23]	BARTHLEMY M . Betweenness centrality in large complex networks[J]. The European Physical Journal B - Condensed Matter, 2004,38(2): 163-168.
[24]	KUMAR P V , BALASUBRAMANIAN C . Trilateral spearman katzcentrality based least angle regression for influential node tracing in social network[J]. Wireless Personal Communications, 2022,122(3): 2767-2790.
[25]	YANG Y Z , WANG X , CHEN Y ,et al. Identifying key nodes in complex networks based on global structure[J]. IEEE Access, 8: 32904-32913.
[26]	IBNOULOUAFI A , EL HAZITI M , CHERIFI H . M-Centrality,identifying key nodes based on global position and local degree variation[J]. Journal of Statistical Mechanics,Theory and Experiment, 2018,2018(7): 073407.
[27]	LI Z , REN T , MA X Q ,et al. Identifying influential spreaders by gravity model[J]. Scientific Reports, 20199,8387.
[28]	ZHUANG Y B , LI Z H , ZHUANG Y J . Identification of influencers in online social networks,measuring influence considering multidimensional factors exploration[J]. Heliyon, 2021,7(4): e06472-327.
[29]	CHIANG M F , LIM E P , LEE W C ,et al. CO2Vec,embeddings of co-ordered networks based on mutual reinforcement[C]// Proceedings of 2020 IEEE 7th International Conference on Data Science and Advanced Analytics. Piscataway,IEEE Press, 2020: 148-157.
[30]	XU Y , FENG Z D , QI X Q . Signless-Laplacian eigenvector centrality:a novel vital nodes identification method for complex networks[J]. Pattern Recognition Letters, 2021,148: 7-14.
[31]	WU X M , WU J S , LI Y F ,et al. Link prediction of time-evolving network based on node ranking[J]. Knowledge-Based Systems, 2020,195,105740.
[32]	PAGE L , BRIN S , MOTWANI R ,et al. The Pagerank citation ranking,bringing order to the Web[EB]. 1998.
[33]	ZHANG Y C , YU J X , HOU J Y ,et al. HITS and related algorithms[EB]. 2006.
[34]	LI Q , ZHOU T , LüL Y , ,et al. Identifying influential spreaders by weighted LeaderRank[J]. Physica A,Statistical Mechanics and Its Applications, 2014,404: 47-55.
[35]	TONG Q , WEI S , CHANG Z . How to identify the most powerful node in complex networks? A novel entropy centrality approach[J]. Entropy, 2017,19(11): 614.
[36]	BARBEHENN M . A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices[J]. IEEE Transactions on Computers, 1998,47(2): 263.
[37]	NIE T Y , GUO Z , ZHAO K ,et al. Using mapping entropy to identify node centrality in complex networks[J]. Physica A,Statistical Mechanics and Its Applications, 2016,453: 290-297.
[38]	MA LL , MA C , ZHANG H F ,et al. Identifying influential spreaders in complex networks based on gravity formula[J]. Physica A,Statistical Mechanics and Its Applications, 2016,451: 205-212.
[39]	ULLAH A , WANG B , SHENG J F ,et al. Identification of nodes in fluence based on global structure model in complex networks[J]. Scientific Reports,2021,11, 6173.

排序	节点	CI
1	6	4.26
2	9	4.14
3	3	3.66
4	12	3.08
5	7	2.39
6	8	2.39
7	10	2.01
8	11	2.01
9	2	1.94
10	4	1.12
11	5	1.12
12	1	0.87

网络	\|M\|	\|N\|	?K?	α	K_max	<CC>
Zebra	111	27	8	1.0	14	0.876
PDZ-base	242	212	2	1.0	21	0.005 3
Air-traffic	2 615	1 226	4.265 9	1.0	37	0.04
E-mail	5 451	1 333	9.615	0.4	71	0.220 2
Friendship	12 534	1 858	5.745	0.2	85	0.167
As-200010	12 572	6474	3.92	0.2	1 458	0.253

基于全局—局部属性的复杂网络节点综合影响力评估算法

Comprehensive influence evaluation algorithm of complex network nodes based on global-local attributes

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 39

相关文章 1

Metrics

推荐阅读 0

排序	BC	CC	GIC	GSM	CI	CI^*	SIR	SIR^*
1	3	6	6	9	6	8.51	6	0.437
2	6	3	9	6	9	8.28	9	0.390
3	9	9	3	3	3	7.32	3	0.333
4	12	7	12	12	12	6.15	12	0.322
5	2	8	7	7	7	4.77	7	0.318
6	1	12	8	8	8	4.77	8	0.285
7	4	2	2	2	10	4.02	10	0.281
8	5	4	10	10	11	4.02	11	0.278
9	7	5	11	11	2	3.87	2	0.256
10	8	11	4	4	4	2.24	4	0.239
11	11	10	5	5	5	2.24	5	0.229
12	10	1	1	1	1	1.73	1	0.186