On the Discovery of Critical Links and Nodes for Assessing Network Vulnerability

The assessment of network vulnerability is of great importance in the presence of unexpected disruptive events or adversarial attacks targeting on critical network links and nodes. In this paper, we study Critical Link Disruptor (CLD) and Critical Node Disruptor (CND) optimization problems to identi...

Full description

Saved in:
Bibliographic Details
Published in:IEEE/ACM transactions on networking 2013-06, Vol.21 (3), p.963-973
Main Authors: Yilin Shen, Nguyen, N. P., Ying Xuan, Thai, M. T.
Format: Article
Language:English
Subjects:
Computational complexity
experiments
IEEE transactions
inapproximability
Internet
Materials
Measurement
Network topology
network Vulnerability
Optimization
Polynomials
Studies
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The assessment of network vulnerability is of great importance in the presence of unexpected disruptive events or adversarial attacks targeting on critical network links and nodes. In this paper, we study Critical Link Disruptor (CLD) and Critical Node Disruptor (CND) optimization problems to identify critical links and nodes in a network whose removals maximally destroy the network's functions. We provide a comprehensive complexity analysis of CLD and CND on general graphs and show that they still remain NP-complete even on unit disk graphs and power-law graphs. Furthermore, the CND problem is shown NP-hard to be approximated within Ω([( n - k )/( n ε )] ) on general graphs with n vertices and k critical nodes. Despite the intractability of these problems, we propose HILPR, a novel LP-based rounding algorithm, for efficiently solving CLD and CND problems in a timely manner. The effectiveness of our solutions is validated on various synthetic and real-world networks.
ISSN:1063-6692
1558-2566
DOI:10.1109/TNET.2012.2215882