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.

Faramondi, L., Oliva, G., Pascucci, F., Panzieri, S., Setola, R. (2016). Critical node detection based on attacker preferences. In 24th Mediterranean Conference on Control and Automation, MED 2016 (pp.773-778). Institute of Electrical and Electronics Engineers Inc. [10.1109/MED.2016.7535859].

Critical node detection based on attacker preferences

FARAMONDI, LUCA;PASCUCCI, Federica;PANZIERI, Stefano;
2016-01-01

Abstract

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.
2016
9781467383455
9781467383455
Faramondi, L., Oliva, G., Pascucci, F., Panzieri, S., Setola, R. (2016). Critical node detection based on attacker preferences. In 24th Mediterranean Conference on Control and Automation, MED 2016 (pp.773-778). Institute of Electrical and Electronics Engineers Inc. [10.1109/MED.2016.7535859].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/310047
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 20
  • ???jsp.display-item.citation.isi??? 15
social impact