Network Vulnerability Assessment Using Critical Nodes Identification

Protecting network applications against malicious behaviors is one of the main concerns when designing network applications. A secured application must take into account any network weakness that an attacker may exploit. One of the major weaknesses is network disconnectivity. A network becomes disconnected by removing nodes/links. This nodes/links are those those that maintain the whole network connectivity, and known as the critical elements. In this paper, we consider the problem of finding critical nodes in networks, which is a good way to assess network vulnerability. This problem consists in finding the smallest subset of nodes, in a given network, the deletion of which partitions it into connected components of the minimum cardinality. We investigate the problem complexity on the class of networks modeled by split graphs, where we show that it remains NP-hard, and hence heuristic approaches are well-suitable for finding near optimal solutions.