A novel algorithm for identifying key nodes in complex networks based on relative entropy and neighbor influence clustering

WANG Haoxiang; CHEN Junxi; WEI Zhenlin; ZHANG Jiaxin

doi:10.11860/j.issn.1673-0291.20230092

Abstract：To address the issue of many key node identification algorithms overlooking the interrelation-ships between nodes and their neighbors when assessing node importance in networks,thereby affect-ing the evaluation of network robustness and vulnerability,an improved local weighted density mea-sure is proposed,named CPR-WCCN. This method aims to accurately identify critical nodes in com-plex networks at a lower computational cost. Firstly,a communication probability sequence between nodes is defined using the shortest path lengths and counts. Secondly,the traditional binary adjacency matrix is transformed into a network normalized correlation matrix by combining Communication Prob-ability and Relative Entropy (CPR).Then,by incorporating Weighted Clustering Coefficients and Neighbor Influence (WCCN),an improved local weighted density is derived,which accounts for neighbor influence. Finally,to validate the effectiveness of the CPR-WCCN algorithm,simulation ex-periments are conducted under both intentional and random attacks. Utilizing a propagation model,a comparative analysis of CPR-WCCN is performed against five other algorithms across four real-world networks. The experimental results indicate that under intentional attacks,where the top 15 critical nodes are disabled,key metrics such as network connectivity,efficiency,maximum connected sub-graph,and natural connectivity show a more significant decline than random attacks. Compared to the other five algorithms,the CPR-WCCN algorithm demonstrates optimal overall performance,which accurately and efficiently identifies critical nodes within the network.