Identifying influential nodes in complex networks: a semi-local centrality measure based on augmented graph and average shortest path theory

Identifying influential nodes in complex networks is a crucial problem in network analysis with broad applications in various fields such as bioinformatics, social engineering, and information dissemination. Existing methods for identifying influential nodes often face challenges such as ignoring semantic relationships and inefficiencies in large-scale networks. This paper presents an efficient multidimensional centrality measure (EMDC) for complex networks that integrates multiple aspects of node influence to address these challenges. The strength of relationships between nodes is obtained through the degree of neighborhood overlap by integrating degree and entropy information. Meanwhile, EMDC combines degree centrality with the k-shell measure to enhance the identification of seed nodes. EMDC develops an augmented graph to measure semantic similarity between nodes by representing distant relationships. Also, EMDC can extract a local subgraph for each node in a distributed manner. Meanwhile, the average shortest path theory, redefined with a semi-local structure, addresses the issue of identifying influential nodes in large-scale networks. The Susceptible-Infected (SI) model and Kendall’s correlation coefficient are used to evaluate the performance of our centrality measure. Experimental results on real-world datasets confirm the superiority of EMDC.