Multiobjective Formulation for Protection Allocation in Interdependent Infrastructure Networks Using an Attack-Diffusion Model
Publication: Journal of Infrastructure Systems
Volume 24, Issue 1
Abstract
Interdependent networks are a collection of individual networks that contain nodes that have interdependent relationships with nodes of other networks. Recognizing that many real-life networks are interdependent, approaches that were previously developed to study vulnerability in single networks are being extended to interdependent network applications (e.g., intentional attack of selected nodes). As such, this study proposes an approach for finding the best set of protection strategies for a given set of interdependent networks exposed to random or intentional attacks through the development of a multiobjective optimization formulation. A simple diffusion model [susceptible-infected-recovered (SIR)], based on cellular automata is used to describe the dynamics of the spread of the disruptive event through each individual network, and Monte Carlo simulation enables simulating the stochastic evolution of the disruption between the nodes of the interdependent networks. Several criteria considering the results of the propagation dynamics in each network or in the whole set of interdependent networks are proposed to assess the security characteristics of the network, and Pareto-optimal solutions are derived using the multiobjective evolutionary Nondominated Sorting Genetic Algorithm (NSGA-II). An example using the topology of an Italian electric power network and the set of communities previously defined illustrates the approach.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
Drs. Barker and Ramirez-Marquez were supported in part by the National Science Foundation, Division of Civil, Mechanical, and Manufacturing Innovation, under Award 1541165.
References
Ahmed, E., and Agiza, H. N. (1998). “On modelling epidemics including latency, incubation, and variable susceptibility.” Physica A, 253(1–4), 347–352.
Amin, M. (2002). “Toward secure and resilient interdependent infrastructures.” J. Infrastruct. Syst., 67–75.
Barker, K., et al. (2017). “Defining resilience analytics for interdependent cyber-physical-social networks.” Sustainable Resilient Infrastruct., 2(2), 59–67.
Beauchemin, C., Samuel, J., and Tuszynski, J. (2005). “A simple cellular automaton model for influenza A viral infections.” J. Theor. Biol., 232(2), 223–234.
Bertotti, M. L., Brunner, J., and Modanese, G. (2016). “The Bass diffusion model on networks with correlations and inhomogeneous advertising.” Chaos, Solitons Fractals, 90, 55–63.
Boccaletti, S., et al. (2014). “The structure and dynamics of multilayer networks.” Phys. Rep., 544(1), 1–122.
Buldyrev, S. V., Parshani, R., Paul, G., Stanley, H. E., and Havlin, S. (2010). “Catastrophic cascade of failures in interdependent networks.” Nature, 464(7291), 1025–1028.
Buldyrev, S. V., Shere, N. W., and Cwilich, G. A. (2011). “Interdependent networks with identical degrees of mutually dependent nodes.” Phys. Rev. E, 83(1), 016112.
Buono, C., Alvarez-Zuzek, L. G., Macri, P. A., and Braunstein, L. A. (2014). “Epidemics in partially overlapped multiplex networks.” PLoS One, 9(3), e92200.
Cantó, B., Coll, C., and Sánchez Cantó, E. (2017). “Estimation of parameters in a structured SIR model.” Adv. Differ. Equ., 2017(1), 33.
Chankong, V., and Haimes, Y. Y. (2008). Multiobjective decision making: Theory and methodology, Dover, Mineola, NY.
Clauset, A., Newman, M., and Moore, C. (2004). “Finding community structure in very large networks.” Phys. Rev. E, 70(6), 066111.
Coello, C. (1999). “A comprehensive survey of evolutionary-based multiobjective optimization techniques.” Knowledge Inf. Syst., 1(3), 129–156.
Cohen, R., Erez, K., Ben-Avraham, D., and Havlin, S. (2000). “Resilience of the Internet to random breakdown.” Phys. Rev. Lett., 85(21), 4626–4628.
Cozzo, E., Ferraz de Arruda, G., Rodrigues, F. A., and Moreno, Y. (2016). “Multilayer networks: Metrics and spectral properties.” Interconnected networks (understanding complex systems), A. Garas, ed., Springer, New York.
Crucitti, P., Latora, V., and Marchiori, M. (2005). “Locating critical lines in high voltage electrical power grids.” Fluctuation Noise Lett., 5(2), L201–L208.
Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T. (2002). “A fast and elitist multiobjective genetic algorithm: NSGA-II.” IEEE Trans. Evol. Comput., 6(2), 182–197.
Dickison, M., Havlin, S., and Stanley, H. E. (2012). “Epidemics on interconnected networks.” Phys. Rev. E, 85(6), 066109.
Diekmann, O., Heesterbeek, J. A. P., and Metz, J. A. J. (1990). “On the definition and the computation of the basic reproduction ratio R0 in models for infectious diseases in heterogeneous populations.” J. Math. Biol., 28(4), 365–382.
Fortunato, S. (2010). “Community detection in graphs.” Phys. Rep., 486(3–5), 75–174.
Fresnadillo Martínez, M. J., García Merino, E., García Sánchez, E., García Sánchez, J. E., Martín del Rey, A., and Rodríguez Sánchez, G. (2013). “A graph cellular automata model to study the spreading of an infectious disease.”, Springer, Berlin, 458–468.
Fuentes, M. A., and Kuperman, M. N. (1999). “Cellular automata and epidemiological models with spatial dependence.” Physica A, 267(3–4), 471–486.
Garas, A. (2016). Interconnected networks, Springer, New York.
Goeyvaerts, N., et al. (2015). “Estimating dynamic transmission model parameters for seasonal influenza by fitting to age and season-specific influenza-like illness incidence.” Epidemics, 13, 1–9.
Gómez, S., Díaz-Guilera, A., Gómez-Gardeñes, J., Pérez-Vicente, C. J., Moreno, Y., and Arenas, A. (2013). “Diffusion dynamics on multiplex networks.” Phys. Rev. Lett., 110(2), 028701.
González, A. D., Dueñas-Osorio, L., Sánchez-Silva, M., and Medaglia, A. L. (2016). “The interdependent network design problem for optimal infrastructure system restoration.” Comput. Aided Civ. Infrastruct. Eng., 31(5), 334–350.
Hethcote, H. (2000). “The mathematics of infectious diseases.” SIAM Rev., 42(4), 599–653.
Holden, R., Val, D. V., Burkhard, R., and Nodwell, S. (2013). “A network flow model for interdependent infrastructures at the local scale.” Saf. Sci., 53(1), 51–60.
Kinney, S., and Peterson, E. (2010). “Modeling of diffusion through a network: A new approach using cellular automata and network science techniques.”, U.S. Military Academy, West Point, NY.
Kivelä, M., Arenas, A., Barthelemy, M., Gleeson, J. P., Moreno, Y., and Porter, M. A. (2014). “Multilayer networks.” J. Complex Networks, 2(3), 203–271.
López, E., Parshani, R., Cohen, R., Carmi, S., and Havlin, S. (2007). “Limited path percolation in complex networks.” Phys. Rev. Lett., 99(18), 188701.
Martín del Rey, A. (2013). “A SIR e-epidemic model for computer worms based on cellular automata.”, Springer, Berlin, 228–238.
Ouyang, M., Hong, L., Mao, Z.-J., Yu, M.-H., and Qi, F. (2009). “A methodological approach to analyze vulnerability of interdependent infrastructures.” Simul. Modell. Pract. Theory, 17(5), 817–828.
Pepyne, D., Panayiotou, C., Cassandras, C., and Ho, Y. (2001). “Vulnerability assessment and allocation of protection resources in power systems.” Proc., IEEE American Control Conf., American Automatic Control Council, Evanston, IL, 4705–4710.
Porter, M. A., and Gleeson, J. P. (2016). Dynamical systems on networks, Springer, New York.
Porter, M. A., Onnela, J.-P., and Mucha, P. J. (2009). “Communities in networks.” Not. Am. Math. Soc., 56(9), 1082–1097.
R version 3.4.3 [Computer software]. R Foundation, Vienna, Austria.
Rahmandad, H., and Sterman, J. (2008). “Heterogeneity and network structure in the dynamics of diffusion: Comparing agent-based and differential equation models.” Manage. Sci., 54(5), 998–1014.
Ramirez-Marquez, J. E., Rocco, C. M., and Barker, K. (2017). “Bi-objective vulnerability reduction formulation for a network under diverse attacks.” J. Risk Uncertainty Eng. Syst., 3(4), 04017025.
Rinaldi, S. M., Peerenboom, J. P., and Kelly, T. K. (2001). “Identifying, understanding and analyzing critical infrastructure interdependencies.” IEEE Control Syst. Mag., 21(6), 11–25.
Rocco, C., and Zio, E. (2005). “Solving advanced network reliability problems by means of cellular automata and Monte Carlo sampling.” Reliability Eng. Syst. Saf., 89(2), 219–226.
Rocco, C. M., Barker, K., Moronta, J., and Ramirez-Marquez, J. E. (2017). “Community detection and resilience in multi-source, multi-terminal networks with application in electric power systems.” J. Risk Reliability, in press.
Rocco, C. M., and Ramirez-Marquez, J. E. (2011). “Vulnerability metrics and analysis for communities in complex networks.” Reliability Eng. Syst. Saf., 96(10), 1360–1366.
Rocco, C. M., Ramirez-Marquez, J. E., and Salazar, D. E. (2010). “Bi and tri-objective optimization in the deterministic network interdiction problem.” Reliability Eng. Syst. Saf., 95(8), 887–896.
Salehi, M., Sharma, R., Marzolla, M., Magnani, M., Siyari, P., and Montesi, D. (2015). “Spreading processes in multilayer networks.” IEEE Trans. Network Sci. Eng., 2(2), 65–83.
Saumell-Mendiola, A., Serrano, M. A., and Boguñá, M. (2012). “Epidemic spreading on interconnected networks.” Phys. Rev. E, 86(2), 026106.
Schneider, C. M., Yazdani, N., Araujo, N. A. M., Havlin, S., and Herrmann, H. J. (2013). “Towards designing robust coupled networks.” Sci. Rep., 3(1), 1969.
Sharkey, T. C., Nurre, S. G., Nguyen, H., and Chow, J. H. (2016). “Identification and classification of restoration interdependencies in the wake of Hurricane Sandy.” J. Infrastruct. Syst., 04015007.
Smith, D., and Moore, L. (2004). “The SIR model for spread of disease—The differential equation model.” ⟨⟩ (Dec., 2004).
Trautmann, H., Steuer, D., and Mersmann, O. (2012). “mco package under R.” ⟨https://cran.r-project.org/package=mco⟩ (Feb. 20, 2016).
Vespignani, A. (2010). “Complex networks: The fragility of interdependency.” Nature, 464(7291), 984–985.
Wang, Y., and Xiao, G. (2011). “Effects of interconnections on epidemics in network of networks.” Proc., Conf. on Wireless Communications, Networks, and Mobile Computing, IEEE, New York, 1–4.
Wang, Z., Wang, Q., and Klinke, D. J., II. (2016). “Simulation study on effects of order and step size of Runge Kutta methods that solve contagious disease and tumor models.” J. Comput. Sci. Syst. Biol., 9(5), 163–172.
Willox, R., Grammaticos, B., Carstea, A. S., and Ramani, A. (2003). “Epidemic dynamics: Discrete-time and cellular automaton models.” Physica A, 328(1–2), 13–22.
Winkler, J., Duenas-Osorio, L., Stein, R., and Subramanian, D. (2011). “Interface network models for complex urban infrastructure systems.” J. Infrastruct. Syst., 138–150.
Wolfram, S. (1985). “Origins of randomness in physical systems.” Phys. Rev. Lett., 55(5), 449–452.
Xiao, S., Xiao, G., and Cheng, T. H. (2010). “Tolerance of local information-based intentional attacks in complex networks.” J. Phys. A, 43(33), 335101.
Yagan, O., Qian, D., Zhang, J., and Cochran, D. (2012). “Optimal allocation of interconnecting links in cyber-physical systems: Interdependence, cascading failures, and robustness.” IEEE Trans. Parall. Distrib. Syst., 23(9), 1708–1720.
Zhang, Y., Yang, N., and Lall, U. (2016). “Modeling and simulation of the vulnerability of interdependent power-water infrastructure networks to cascading failures.” J. Syst. Sci. Syst. Eng., 25(1), 102–118.
Zhuang, Y., and Yagan, O. (2015). “Information propagation in clustered multilayer networks.” IEEE Trans. Network Sci. Eng., 3(4), 211–224.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 24 • Issue 1 • March 2018
Copyright
©2018 American Society of Civil Engineers.
History
Received: Apr 3, 2017
Accepted: Sep 11, 2017
Published online: Jan 11, 2018
Published in print: Mar 1, 2018
Discussion open until: Jun 11, 2018
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.