Critical node detection based on attacker preferences

The identification of Critical Nodes in technological, biological and social networks is a fundamental task in order to comprehend the behavior of such networks and to implement protection or intervention strategies aimed at reducing the network vulnerability. In this paper we focus on the perspective of an attacker that aims at disconnecting the network in several connected components, and we provide a formulation of the attacker behavior in terms of an optimization problem with two concurrent objectives: maximizing the damage dealt while minimizing the cost or effort of the attack. Such objectives are mediated according to the subjective preferences of the attacker. Specifically, the attacker identifies a set of nodes to be removed in order to disconnect the network in at least m connected components; the final objective is from one side to minimize the number of attacked nodes, and from another side to minimize the size of the largest connected component. We complement the paper by providing an heuristic approach to calculate an admissible solution to the problem at hand, based on the line graph of the original network topology and on the spectral clustering methodology.