Identification of Vital Nodes in Complex Network via Belief Propagation and Node Reinsertion

Vital nodes play a pivotal part of network structure and dynamics, where finding the minimal size of a set of vital nodes belongs to an NP-hard problem and cannot be solved by a polynomial algorithm. Recent studies of vital nodes identification mostly rely on the structural information, such as collective influence and degree. However, the performance of local-based methods varies for different structure, while the complexities of global-based methods are generally high for most situations. Here, we map the problem into an optimization issue based on global information of network structure and propose a belief propagation and node reinsertion (BPR) method with almost linear time complexity, where finding the minimum feeding back vertex set is a key. Compared with several state-of-the-art heuristic methods, the BPR method has advantages of high accuracy and practicability of vital nodes identification and low computational complexity. Under two attack schemes: static and dynamical, extensive experiments of Erdos-Rényi and scale-free models and real-world networks of the power grid and traffic network convincingly demonstrate that the BPR method remarkably outperforms other methods in vital nodes identification. This helps to reassess the operational risk of a network and improve robustness ranging from network design schemes, protection strategies to failure mitigation.