Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach



Assane Gueye, Vladimir V. Marbukh


In this paper, we propose a quantification of the vulnerability of a communication network when links are subject to failures due to the actions of a strategic adversary. We model the adversarial nature of the problem as a 2-player game between a network manager who chooses a spanning tree of the network as communication infrastructure and an attacker who is trying to disrupt the communication by attacking a link. We use previously proposed models for the value of a network to derive payoffs of the players and propose the network’s expected loss-in-value as a metric for vulnerability. In the process, we generalize the notion of betweenness centrality: a metric largely used in Graph Theory to measure the relative importance of a link within a network. Furthermore, by computing and analyzing the Nash equilibria of the game, we determine the actions of both the attacker and the defender. The analysis reveals the existence of subsets of links that are more critical than the others. We characterize these critical subsets of links and compare them for the different network value models. The comparison shows that critical subsets depend both on the value model and on the connectivity of the network. Knowing the critical parts of a network is crucial for network design and improvement. We describe an efficient algorithm that can be used to compute critical subsets of a graph.
IEEE Journal on Selected Areas in Communications


Communication Network Security, Vulnerability Metric, Game Theory


Gueye, A. and Marbukh, V. (2012), Towards a Metric for Communication Network Vulnerability to Attacks: A Game Theoretic Approach, IEEE Journal on Selected Areas in Communications, [online], (Accessed May 19, 2024)


If you have any questions about this publication or are having problems accessing it, please contact

Created February 13, 2012, Updated February 19, 2017