Semilocal Average Shortest Path With Augmented Graph for Identifying Influential Nodes
Lixia Luo, Qitao Tang, Yingying Ma, Amin Rezaeipanah
Abstract
Efficient identification of influential nodes is crucial in complex networks due to its significant theoretical and practical implications for information propagation and various applications. Despite numerous approaches being developed, many existing methods rely on centrality metrics that have inherent deficiencies and limitations. These approaches face challenges such as network sparsity and ignoring relationships between distant nodes. To address these issues, this article proposes an efficient and influential node identification approach named semilocal (SL) average shortest path with augmented graph (ASPAG). We configure the average shortest path (ASP) theory with the extended neighborhood concept to address the network sparsity problem with less complexity. The aim is to develop a SL centrality metric based on ASP that can extract a local subgraph for each node in a distributed manner. ASPAG, on the other hand, uses a combined augmented graph and the SL ASP centrality metric to improve the representation of global relationships in the network and make the most of relationships between nodes that are far apart. By leveraging local topological information and incorporating additional graph structures, our method provides a comprehensive analysis of node influence. Extensive experiments on real-world networks demonstrate that ASPAG outperforms traditional centrality metrics and other state-of-the-art techniques in terms of computational efficiency. Specifically, ASPAG improves Kendall’s τ coefficient under the susceptible-infected-recovered (SIR) model by 4.6% compared to the best available method.