Community Detection in Action: Identification of Critical Elements in Infrastructure Networks
Publication: Journal of Infrastructure Systems
Volume 24, Issue 1
Abstract
Modern infrastructure systems form complex networks that are organized hierarchically in communities of tightly integrated elements. This paper presents three new community-based metrics to identify the critical elements of a network system. Two of these metrics assess intracommunity and intercommunity behavior for any community structure, and the third metric accounts for the multiple levels of community structure. First, these metrics are studied to establish their characteristics with different community structures, and then the Great Britain Railway Network is used as a case study to demonstrate the usefulness of these new metrics. The results show that an assessment of the system using these metrics leads to the identification of not only those elements that are critical at the global level, but also those that greatly affect the local performance of the communities. Such identification of the critical components at the community and global levels would enable a better understanding of system behavior by stakeholders with competing demands.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
All of the numerical experiments were carried out in a MATLAB programming environment, using the MATLABBGL library as a support for component identification, the Graph Theory Toolbox for shortest path computations, and the Community Detection Toolbox for its implementation of the stability optimization algorithm. The authors would like to thank the EPSRC (DTA Grant EP/L504919/1) and the Systems Centre at the University of Bristol, the EPSRC-funded Industrial Doctorate Centre in Systems (Grant EP/G037353/1) for financial support to the first author. The funding organizations were not involved in the design of the study or in the writing of the report. The authors also thank the anonymous reviewers for their constructive comments.
References
Albert, R., Albert, I., and Nakarado, G. L. (2004). “Structural vulnerability of the North American power grid.” Phys. Rev. E Stat. Nonlinear Soft Matter Phys., 69, 25103.
Barabasi, A., and Albert, R. (2002). “Statistical mechanics of complex networks.” Rev. Mod. Phys., 74(1), 47–97.
Barabási, A.-L. (2009). “Scale-free networks: A decade and beyond.” Science 325(5939), 412–413.
Barabási, A.-L. (2016). Network science, Cambridge University Press, Cambridge, U.K.
Barthélemy, M. (2011). “Spatial networks.” Phys. Rep., 499(1–3), 1–101.
Blockley, D., and Godfrey, P. (2000). Doing it differently: Systems for rethinking construction, Thomas Telford, London.
Borgatti, S. P. (2005). “Centrality and network flow.” Soc. Networks, 27(1), 55–71.
Bye, B. L. (2011). “Volcanic eruptions: Science and management.” http://www.science20.com/planetbye/volcanic_eruptions_science_and_risk_management-79456, (May 27, 2011).
Cai, K.-Q., Zhang, J., Du, W., and Cao, X. (2012). “Analysis of the Chinese air route network as a complex network.” Chin. Phys. B, 21(2), 28903.
Cardillo, A., Zanin, M., Gómez-Gardenes, J., Romance, M., del Amo, A. J. G., and Boccaletti, S. (2013). “Modeling the multi-layer nature of the European air transport network: Resilience and passengers re-scheduling under random failures.” Eur. J. Phys. Spec. Top., 215(1), 23–33.
Carvalho, R., Buzna, L., Bono, F., Masera, M., Arrowsmith, D. K., and Helbing, D. (2014). “Resilience of natural gas networks during conflicts, crises and disruptions.” PloS One, 9(3), e90265.
Dalziell, E., and Nicholson, A. (2001). “Risk and impact of natural hazards on a road network.” J. Transp. Eng., 159–166.
Danon, L., Díaz-Guilera, A., and Arenas, A. (2006). “The effect of size heterogeneity on community identification in complex networks.” J. Stat. Mech. Theory Exp., 2006(11), P11010–P11010.
DeLaurentis, D., Han, E.-P., and Kotegawa, T. (2008). “Network-theoretic approach for analyzing connectivity in air transportation networks.” J. Aircr., 45(5), 1669–1679.
Delvenne, J.-C., Yaliraki, S. N., and Barahona, M. (2010). “Stability of graph communities across time scales.” Proc. Natl. Acad. Sci. USA, 107(29), 12755–12760.
Dueñas-Osorio, L., Craig, J. I., Goodno, B. J., and Bostrom, A. (2007). “Interdependent response of networked systems.” J. Infrastruct. Syst., 185–194.
Dunn, S., Wilkinson, S., and Ford, A. (2016). “Spatial structure and evolution of infrastructure networks.” Sustainable Cities Soc., 27(Nov), 23–31.
Dunn, S., and Wilkinson, S. M. (2013). “Identifying critical components in infrastructure networks using network topology.” J. Infrastruct. Syst., 157–165.
England, J., Blockley, D., and Agarwal, J. (2008). “The vulnerability of structures to unforeseen events.” Comput. Struct., 86(10), 1042–1051.
Erdos, P., and Renyi, A. (1959). “On random graphs.” Publicationes Mathematicae Debrecen, 6, 290–297.
Fang, Y., Pedroni, N., and Zio, E. (2015). “Optimization of cascade-resilient electrical infrastructures and its validation by power flow modeling.” Risk Anal., 35(4), 594–607.
Fang, Y.-P., and Zio, E. (2013). “Unsupervised spectral clustering for hierarchical modelling and criticality analysis of complex networks.” Reliab. Eng. Syst. Saf., 116(Aug), 64–74.
Fortunato, S. (2010). “Community detection in graphs.” Phys. Rep., 486(3–5), 75–174.
Fortunato, S., and Barthelemy, M. (2007). “Resolution limit in community detection.” Proc. Natl. Acad. Sci. USA, 104(1), 36–41.
Galvan, G., and Agarwal, J. (2015). “Community detection and infrastructural criticality.” Safety and reliability of complex engineered systems: ESREL 2015, Podofillini, L., Sudret, B., Stojadinovic, B., Zio, E., and Kröger, W., eds., CRC Press, London, 1209–1217.
Gómez, C., Sánchez-Silva, M., and Dueñas-Osorio, L. (2014). “An applied complex systems framework for risk-based decision-making in infrastructure engineering.” Struct. Saf., 50(Sep), 66–77.
Grubesic, T. H., and Murray, A. T. (2006). “Vital nodes, interconnected infrastructures, and the geographies of network survivability.” Ann. Assoc. Am. Geograph., 96(1), 64–83.
Hong, L., Ouyang, M., Peeta, S., He, X., and Yan, Y. (2015). “Vulnerability assessment and mitigation for the Chinese railway system under floods.” Reliab. Eng. Syst. Saf., 137(May), 58–68.
Johansson, J., and Hassel, H. (2010). “An approach for modeling interdependent infrastructures in the context of vulnerability analysis.” Reliab. Eng. Syst. Saf., 95(12), 1335–1344.
Johansson, J., and Hassel, H. (2014). “Impact of functional models in a decision context of critical infrastructure vulnerability reduction.” Vulnerability, uncertainty, and risk: Quantification, mitigation, and management, Beer, M., Au, S.-K., and Hall, J. W., eds., ASCE, Reston, VA, 577–586.
Kurant, M., and Thiran, P. (2006). “Extraction and analysis of traffic and topologies of transportation networks.” Phys. Rev. E, Stat. Nonlinear Soft Matter Phys., 74(3 Pt 2), 36114.
Kurant, M. I., Thiran, P., and Hagmann, P. (2007). “Error and attack tolerance of layered complex networks.” Phys. Rev. E Stat. Nonlinear Soft Matter Phys., 76(2), 1–5.
Lambiotte, R. (2010). “Multi-scale modularity in complex networks.” Proc., 8th Int. Symp. on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt), IEEE, New York, 546–553.
Lämmer, S., Gehlsen, B., and Helbing, D. (2006). “Scaling laws in the spatial structure of urban road networks.” Phys. A Stat. Mech. Appl., 363(1), 89–95.
Latora, V., and Marchiori, M. (2007). “A measure of centrality based on network efficiency.” New J. Phys., 9(6), 188.
Le Martelot, E., and Hankin, C. (2011). “Multi-scale community detection using stability optimisation within greedy algorithms.” Proc., Int. Conf. on Knowledge Discovery and Information Retrieval, SciTePress, Setúbal, Portugal, 216–225.
Lorenz, J., Battiston, S., and Schweitzer, F. (2009). “Systemic risk in a unifying framework for cascading processes on networks.” Eur. Phys. J. B, 71(4), 441–460.
MATLAB [Computer software]. MathWorks, Natick, MA.
Mattsson, L., and Jenelius, E. (2015). “Vulnerability and resilience of transport systems—A discussion of recent research.” Transp. Res. Part A, 81(Nov), 16–34.
Mena, R., Hennebel, M., Li, Y.-F., and Zio, E. (2014). “Self-adaptable hierarchical clustering analysis and differential evolution for optimal integration of renewable distributed generation.” Appl. Energy, 133, 388–402.
Mossa, S., Turtschi, A., and Amaral, L. A. (2005). “The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles.” Proc. Natl. Acad. Sci. USA, 102(22), 7794–7799.
Mureddu, M., Caldarelli, G., Chessa, A., Scala, A., and Damiano, A. (2015). “Green power grids: How energy from renewable sources affects networks and markets.” PLoS one, 10(9), e0135312.
Murray, A. T., Grubesic, T. H., and Matisziw, T. C. (2008). “A methodological overview of network vulnerability analysis.” Growth Change, 39(4), 573–592.
National Rail. (2015). “Maps of the UK railway network.” ⟨http://www.nationalrail.co.uk/stations_destinations/maps.aspx⟩ (Oct. 31, 2017).
Network Rail. (2014). “Dawlish.” ⟨http://www.networkrail.co.uk/timetables-and-travel/storm-damage/dawlish/⟩ (Mar. 31, 2014).
Newman, M., and Girvan, M. (2004). “Finding and evaluating community structure in networks.” Phys. Rev. E, 69(2), 26113.
Office of Rail and Road. (2015). “Station usage 2014–2015 data.” ⟨http://orr.gov.uk/__data/assets/excel_doc/0019/20179/Estimates-of-Station-Usage-in-2014-15.xlsx⟩ (Oct. 31, 2017).
Ouyang, M. (2013). “Comparisons of purely topological model, betweeness based model and direct current power flow model to analyze power grid vulnerability.” Chaos, 23(2), 023114.
Ouyang, M. (2014).“Review on modeling and simulation of interdependent critical infrastructure systems.” Reliab. Eng. Syst. Saf., 121, 43–60.
Ouyang, M., Hong, L., Mao, Z.-J., Yu, M.-H., and Qi, F. (2009). “A methodological approach to analyze vulnerability of interdependent infrastructure.” Simul. Modell. Pract. Theory, 17(5), 817–828.
Ouyang, M., Pan, Z., Hong, L., and Zhao, L. (2014). “Comparisons of complex network based models and real train flow model to analyze Chinese railway vulnerability.” Reliab. Eng. Syst. Saf., 123(Mar), 38–46.
Poljansek, K., Gutierrez, E., and Bono, F. (2012). “Seismic risk assessment of interdependent critical infrastructure systems: The case of European gas and electricity networks.” Earthquake Eng. Struct. Dyn., 41(1), 61–79.
Reggiani, A., Nijkamp, P., and Lanzi, D. (2015). “Transport resilience and vulnerability: The role of connectivity.” Transp. Res. Part A, 81(Nov), 4–15.
Reichardt, J., and Bornholdt, S. (2006). “Statistical mechanics of community detection.” Phys. Rev. E, 74(1), 016110.
Rocco, C. M., and Ramirez-Marquez, J. E. (2011). “Vulnerability metrics and analysis for communities in complext networks.” Reliab. Eng. Syst. Saf., 96(10), 1360–1366.
Sen, P., Dasgupta, S., Chatterjee, A., Sreeram, P. A., Mukherjee, G., and Manna, S. S. (2003). “Small-world properties of the Indian railway network.” Phys. Rev. E, 67, 36106.
Strano, E., Cardillo, A., Iacoviello, V., Latora, V., Messora, R., Porta, S., and Scellato, S. (2007). “Street centrality vs. commerce and service locations in cities: A kernel density correlation case study in Bologna, Italy.” ArXiv e-prints arXiv:physics/0701111.
United Nations International Strategy for Disaster Reduction (UNISDR). (2015). “Sendai framework for disaster risk reduction.” ⟨http://www.preventionweb.net/files/43291_sendaiframeworkfordrren.pdf⟩ (Oct. 31, 2017).
Vugrin, E. D., Warren, D. E., and Ehlen, M. A. (2011). “A resilience assessment framework for infrastructure and economic systems: Quantitative and qualitative resilience analysis of petrochemical supply chains to a hurricane.” Process Saf. Prog., 30(3), 280–290.
Wilkinson, S. M., Dunn, S., and Ma, S. (2012). “The vulnerability of the European air traffic network to spatial hazards.” Nat. Hazard., 60(3), 1027–1036.
Yazdani, A., and Jeffrey, P. (2011). “Complex network analysis of water distribution systems.” Chaos, 21(1), 16111.
Zio, E. (2016). “Challenges in the vulnerability and risk analysis of critical infrastructures.” Reliab. Eng. Syst. Saf., 152(Aug), 137–150.
Zio, E., and Sansavini, G. (2013). “Vulnerability of smart grids with variable generation and consumption: A system of systems perspective.” IEEE Trans. Syst. Man Cybern. Syst., 43(3), 477–487.
Zio, E., Sansavini, G., Maja, R., and Marchionni, G. (2011). “An analytical approach to the safety of road networks.” Int. J. Reliab, Qual. Saf. Eng., 15(1), 67–76.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 24 • Issue 1 • March 2018
Copyright
©2017 American Society of Civil Engineers.
History
Received: Oct 21, 2016
Accepted: Jun 9, 2017
Published online: Nov 28, 2017
Published in print: Mar 1, 2018
Discussion open until: Apr 28, 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.