Journal
IEEE-ACM TRANSACTIONS ON NETWORKING
Volume 20, Issue 2, Pages 609-619Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TNET.2011.2170849
Keywords
Approximation algorithm; hardness; network vulnerability; pairwise connectivity
Categories
Funding
- Division Of Computer and Network Systems
- Direct For Computer & Info Scie & Enginr [0953284] Funding Source: National Science Foundation
Ask authors/readers for more resources
Society relies heavily on its networked physical infrastructure and information systems. Accurately assessing the vulnerability of these systems against disruptive events is vital for planning and risk management. Existing approaches to vulnerability assessments of large-scale systems mainly focus on investigating inhomogeneous properties of the underlying graph elements. These measures and the associated heuristic solutions are limited in evaluating the vulnerability of large-scale network topologies. Furthermore, these approaches often fail to provide performance guarantees of the proposed solutions. In this paper, we propose a vulnerability measure, pairwise connectivity, and use it to formulate network vulnerability assessment as a graph-theoretical optimization problem, referred to as beta-disruptor. The objective is to identify the minimum set of critical network elements, namely nodes and edges, whose removal results in a specific degradation of the network global pairwise connectivity. We prove the NP-completeness and inapproximability of this problem and propose an O(log n log log n) pseudo-approximation algorithm to computing the set of critical nodes and an O(log(1.5) n) pseudo-approximation algorithm for computing the set of critical edges. The results of an extensive simulation-based experiment show the feasibility of our proposed vulnerability assessment framework and the efficiency of the proposed approximation algorithms in comparison to other approaches.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available