System vulnerability assessment and critical nodes identification

Critical nodes in complex systems need to be identified for protection or removal. Removal of critical nodes decreases or minimizes a system's ability to diffuse entities such as information, goods, or diseases. Previous research suggested some vulnerability metrics, but there remains a lack of understanding how a metric changes (e.g., upper bound and lower bound) and how it is related to the structure of a complex system. This research designs three metrics to assess system vulnerability, and analyzes their characteristics over different system structures. A polynomial-time algorithm using the three metrics is developed to identify critical nodes step by step (local optima). Their performance are examined and compared to other algorithms. The three metrics designed in this article are informative and their characteristics are thoroughly analyzed for various system structures. The metrics and algorithm may be used by domain experts to effectively assess system vulnerability and identify critical nodes.