Identifying vital nodes of complex networks with an improved gravity model aware of structural damage and embedding

Abstract Identifying vital nodes of complex networks is essential for protecting networks from attack, with the gravity-based methods providing an effective approach. Most existing methods merely consider the network static topology, however, the structural damage under attack is rarely taken into account. Moreover, many methods emphasize the network topological feature, but lack consideration of the node embeddings. In this article, we propose a novel gravity model by quantifying the structural damage with the network dismantling, and comprehensively incorporating both the structural and embedding features. Examining how the node removal impairs the network topology well captures the node influence on the network structure, while the node embeddings learned by graph machine learning reveal the low-dimensional features of nodes. Two metrics, the relative size of the largest connected component and network efficiency, are employed to evaluate network fragility under attack. Experiments on six real-world networks demonstrate that, compared with nine baseline methods, the proposed approach results in the most severe network fragmentation by removing fewest vital nodes, indicating its superiority in vital node identification. Furthermore, spreading ability is assessed by the SIR model, and the proposed method exhibits an advantage in spreading performance.