Network topology vulnerability/cost trade-off: Model, application, and computational complexity

Aron Laszka, Assane Gueye

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


Technological networks (e.g., telephone and sensor networks, Internet) have provided modern society with increased efficiency, but have also exposed us to the risks posed by their vulnerability to attacks. Mitigating these risks involves designing robust network topologies in situations where resources are economically constrained. In this study, we consider the vulnerability of network topologies from an economic viewpoint and propose security metrics, which are necessary for assessing the efficiency of our solutions. We define the vulnerability of a network as the potential loss in connectivity due to the actions of a strategic adversary. To derive vulnerability metrics, we revisit our recently introduced network blocking game models, which provide a framework for quantifying network topology vulnerability in adversarial environments. We assume that the network operator takes both security and economic goals into consideration. To model these goals, we generalize previous models by introducing usage costs and budget constraints for the operator. We study two natural constraint formulations, the maximum and the expected cost constraints, and derive the feasible vulnerability/cost region. Because the proposed metrics are based on game-theoretic models, computing them can be challenging. To elucidate these challenges, we provide a thorough complexity analysis for solving the proposed games.

Original languageEnglish (US)
Pages (from-to)588-626
Number of pages39
JournalInternet Mathematics
Issue number6
StatePublished - 2015

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Network topology vulnerability/cost trade-off: Model, application, and computational complexity'. Together they form a unique fingerprint.

Cite this