Implementation of multi-objective optimization for vulnerability analysis of complex networks

Abstract

This paper describes the vulnerability analysis of a complex network as the process of identifying the combination of component failures that provide maximum reduction of network performance. By way of a vulnerability analysis, the understanding of these failures can be related to the occurrence of a disruptive event, and also to the fundamental tasks for the protection of critical infrastructures. To describe vulnerability, the paper provides an analytical method to characterize completely the importance of network disruptions and identify a vulnerability set via the solution of a proposed multi-objective network vulnerability problem. This approach makes it possible to recognize that decision-makers (e.g. network managers) could benefit from understanding the relationship between different failure scenarios and network performance, for example, how the increase in protection resources would reduce the vulnerability of the network. Numerical examples, related to a medium-sized network and two complex networks, are solved using the evolutionary algorithm known as the multi-objective probabilistic solution discovery algorithm (MO-PSDA) and illustrate the proposed approach.

Keywords

network vulnerability multi-objective optimization evolutionary algorithms sensitivity analysis

Get full access to this article

View all access options for this article.

References

Prezant

Clair

Belyaev

Alleyne

Banauch

Davitt

Vandervoorts

Kelly

Currie

Kalkut

‘Effects of the August 2003 blackout on the New York City healthcare delivery system: A lesson for disaster preparedness’

Critical Care Medicine 33 (1)(suppl.) (2005): S96-S101.

Berdica

‘An introduction to road vulnerability: what has been done, is done and should be done’

Transp. Policy 9 (2) (2002): 117–127

Crucitti

Latora

Marchiori

‘Locating critical lines in high-voltage electric power grids’

Fluctuation and Noise Lett. 5 (2) (2005): L201-L208.

Rosato

Issacharoff

Bologna

‘Influence of the topology on the power flux of the Italian high-voltage electrical network’

Europhysics Lett. (2009): (in press)

Newman

M. E. J.

Girvan

Finding and evaluating community structure in networks, 2003, available from http://arxiv.org/abs/cond-mat/0308217.

Nagurney

Qiang

Q. A

‘Transportation network efficiency measure that captures flows, behavior, and costs with applications to network component importance identification and vulnerability’. In Proceedings of the POMS 18th Annual Conference, 4–7 May 2007.

Nagurney

Qiang

Q. A

‘A network efficiency measure for congested networks’

EPL 79 (38005) (2007): DOI: 10.1209/0295–5075/79/38005.

Nagurney

Qiang

Q. A

‘Robustness of transportation networks subject to degradable links’

Europhysics Lett. 80 (2007): 1–6

Zio

Sansavini

Maja

Marchionni

‘An analytical approach to the safety of road networks’

Int. J. Reliability, Qual. Saf. Engng 15 (1) (2008): 67–76

10.

Latora

Marchiori

‘Efficient behavior of small-world networks’

Phys. Rev. Lett. 87 (2001): article no. 198701.

11.

Latora

Marchiori

‘Vulnerability and protection of infrastructure networks’

Phys. Rev. E 015103 (R) (2005): pp. 1–4

12.

Crucitti

Latora

Marchiori

‘A topological analysis of the Italian electric power grid’

Physica A 338 (2004): 92–97

13.

Ramirez-Marquez

J. E

Rocco

‘All-terminal network reliability optimization via probabilistic solution discovery’

Reliability Engng System Saf. 93 (11) (2008): 1689–1697

14.

Wood

Wollenberg

Power generation operation and control (New York: John Wiley 1996)

15.

Billinton

Reliability assessment of electric power systems using Monte Carlo methods (New York: Plenum Press 1994)

16.

Rocco

S. C. M.

Ramirez-Marquez

J. E.

Salazar

A. D. E.

Zio

‘A flow importance measure with application to an Italian transmission power system’

Int. J. Performability Engng 6 (1) (2010): 53–61

17.

Boccaletti

Latora

Moreno

Chavez

Hwang

D. U

‘Complex networks: Structure and dynamics’

Physics Rep. 424 (2006): 175–308

18.

Zio

‘From complexity science to reliability efficiency: a new way of looking at complex network systems and critical infrastructures’

Int. J. Critical Infrastructures 3 (2007): 488–508

19.

Salazar

A. D. E.

Rocco

S. C. M.

Zio

‘Optimal protection of complex networks exposed to terrorist hazard: a multi-objective evolutionary approach’

Proc. IMechE, Part O: J. Risk and Reliability 222 (O3) (2008): 327–335 DOI:10.1243/1748006XJRR133.

20.

Rocco

S. C. M.

Salazar

A. D. E.

Zio

‘Application of advanced computational techniques to the vulnerability assessment of network systems exposed to uncertain harmful events’

Int. J. Performability Engng 5 (1) (2009): 71–84

21.

Zitzler

Laumanns

Thiele

‘SPEA2: improving the strength Pareto evolutionary algorithm. Evolutionary methods for design, optimization and control with applications to industrial problems’ (2002)

22.

Corne

Jerram

Knowles

Oates

‘PESA-II: region-based selection in evolutionary multiobjective optimization’ (2001)

23.

Deb

Pratap

Agarwal

Meyarivan

‘A fast and elitist multiobjective genetic algorithm: NSGA-II’

IEEE Trans. Evolutionary Comput. 6 (2) (2002): 182–197

24.

Rocco

Salazar

Ramirez-Marquez

J. E

‘Multi-objective network onterdiction using evolutionary algorithms’. In Proceedings of The Annual Reliability and Maintainability Symposium, Fort Worth, Texas, January 2009, pp. 170–175.

25.

Rocco

S. C. M.

Ramirez-Marquez

J. E.

Salazar

A. D. E.

‘A multiple-objective approach for the vulnerability assessment of infrastructure networks’. Proceedings of the ESREL Conference (in press).

26.

Manzi

Labbé

Latouche

Maffioli

‘Fishman's sampling plan for computing network reliability’

IEEE Trans. Reliability 50 (1) (2001): 41–46

27.

Rocco

S. C. M.

‘Analysis of the Venezuelan electric power grid through complex network concepts’

Revista de la Facultad de Ingeniería de la U.C.V. 23 (1) (2008): 103–109 (in Spanish)