TY - GEN
T1 - On approximation of new optimization methods for assessing network vulnerability
AU - Dinh, Thang N.
AU - Xuan, Ying
AU - Thai, My T.
AU - Park, E. K.
AU - Znati, Taieb
PY - 2010
Y1 - 2010
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=77953295879&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953295879&partnerID=8YFLogxK
U2 - 10.1109/INFCOM.2010.5462098
DO - 10.1109/INFCOM.2010.5462098
M3 - Conference contribution
AN - SCOPUS:77953295879
SN - 9781424458363
T3 - Proceedings - IEEE INFOCOM
BT - 2010 Proceedings IEEE INFOCOM
T2 - IEEE INFOCOM 2010
Y2 - 14 March 2010 through 19 March 2010
ER -