On approximation of new optimization methods for assessing network vulnerability

Thang N. Dinh, Ying Xuan, My T. Thai, E. K. Park, Taieb Znati

Research output: Chapter in Book/Report/Conference proceedingConference contribution

63 Citations (Scopus)


Assessing network vulnerability before potential disruptive events such as natural disasters or malicious attacks is vital for network planning and risk management. It enables us to seek and safeguard against most destructive scenarios in which the overall network connectivity falls dramatically. Existing vulnerability assessments mainly focus on investigating the inhomogeneous properties of graph elements, node degree for example, however, these measures and the corresponding heuristic solutions can provide neither an accurate evaluation over general network topologies, nor performance guarantees to large scale networks. To this end, in this paper, we investigate a measure called pairwise connectivity and formulate this vulnerability assessment problem as a new graph-theoretical optimization problem called β-disruptor, which aims to discover the set of critical node/edges, whose removal results in the maximum decline of the global pairwise connectivity. Our results consist of the NP-Completeness and inapproximability proof of this problem, an O(log n log log n) pseudo-approximation algorithm for detecting the set of critical nodes and an O(log1.5 n) pseudo-approximation algorithm for detecting the set of critical edges. In addition, we devise an efficient heuristic algorithm and validate the performance of the our model and algorithms through extensive simulations.

Original languageEnglish
Title of host publication2010 Proceedings IEEE INFOCOM
Publication statusPublished - 2010
Externally publishedYes
EventIEEE INFOCOM 2010 - San Diego, CA, United States
Duration: Mar 14 2010Mar 19 2010

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


ConferenceIEEE INFOCOM 2010
Country/TerritoryUnited States
CitySan Diego, CA

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'On approximation of new optimization methods for assessing network vulnerability'. Together they form a unique fingerprint.

Cite this