Identifying Critical Components in Infrastructure Networks Using Network Topology
Publication: Journal of Infrastructure Systems
Volume 19, Issue 2
Abstract
This paper applies graph theory metrics to network flow models, with the aim of assessing the possibility of using these metrics to identify vulnerable areas within infrastructure systems. To achieve this, a reduced complexity flow model that can be used to simulate flows in infrastructure networks is developed. The reason for developing this model is not to make the analysis easier, but to reduce the physical problem to its most basic level and therefore produce the most general flow model (i.e., applicable to the widest range of infrastructure networks). An initial assessment of the applicability of graph theory metrics to infrastructure networks is made by comparing the distribution of flows, calculated using this model, to the shortest average path length in three of the most recognized classes of network—scale-free networks, small-world networks, and random graph models—and it is demonstrated that for all three classes of network there is a strong correlation. This suggests that at least parts of graph theory may be used to inform one about the behavior of physical networks. The authors further demonstrate the utility of graph theory metrics by using them to improve their predictive skill in identifying vulnerable areas in a specific type of infrastructure system. This is done using a hydraulic model to calculate the flows in a sample water distribution network and then to show that using a combination of graph theory metrics and flow gives superior predictive skill over just one of these measures in isolation.
Get full access to this article
View all available purchase options and get full access to this article.
Acknowledgments
This research was funded by the Engineering and Physical Sciences Research Council, UK, and its support is gratefully acknowledged. All of the networks used in this paper were generated using Network Workbench, the shortest average path length was also calculated using Network Workbench, and the three centrality measures were calculated using Pajek (Batagelj and Mrvar 2003).
References
Albert, R., Jeong, H., and Barabasi, A. L. (2000). “Error and attack tolerance of complex networks.” Nature, 406(6794), 378–382.
Albert, R., and Barabasi, A.-L. (2002). “Statistical mechanics of complex networks.” Rev. Modern Phys., 74(1), 47–97.
Barabasi, A. L., Albert, R., and Jeong, H. (2000). “Scale-free characteristics of random networks: The topology of the world-wide web.” Phys. Stat. Mech. Appl., 281(1–4), 69–77.
Barabasi, A.-L., and Albert, R. (1999). “Emergence of scaling in random networks.” Science, 286(5439), 509–512.
Barabasi, A.-L., and Oltvai, Z. N. (2004). “Network biology: Understanding the cell’s functional organization.” Nat. Rev. Genet., 5(2), 101–113.
Batagelj, V., and Mrvar, A. (2003). “Pajek: Program for large network analysis.” 〈http://vlado.fmf.uni-lj.si/pub/networks/pajek〉 (Jul. 1, 2011).
Boccaletti, S., Latora, V., Moreno, Y., Chavez, M., Hwang, D. U. (2006). “Complex networks: Structure and dynamics.” Phys. Rep., 424(4–5), 175–308.
Cadini, F., Zio, E., and Petrescu, C.-A. (2009). “Using centrality measures to rank the importance of the components of a complex network infrastructure.” Critical information infrastructure security, R. Setola and S. Geretshuber, eds., Springer, Berlin, 155–167.
Choi, J. H., Barnett, G. A., and Chon, B.-S. (2006). “Comparing world city networks: a network analysis of Internet backbone and air transport intercity linkages.” Global Network., 6(1), 81–99.
Crucitti, P., Latora, V., and Marchiori, M. (2005). “Locating critical lines in high-voltage electrical power grids.” Fluctuation Noise Letters, 5(2), L201–L208.
Crucitti, P., Latora, V., and Porta, S. (2006). “Centrality in networks of urban streets.” Chaos, 16(1), 015113.
Da Costa, L. F., et al. (2011). “Analyzing and modeling real-world phenomena with complex networks: A survey of applications.” Adv. Phys., 60(3), 329–412.
De Nooy, W., Mrvar, A., and Batagelj, V. (2005). Exploratory social network analysis with Pajek, Cambridge University Press, Cambridge, UK.
Erdös, P., and Renyi, A. (1960). “On the evolution of random graphs.” Publ. Math. Inst. Hung. Acad. Sci., 5, 17–61.
Everett, M. G., and Borgatti, S. P. (1999). “The centrality of groups and classes.” J. Math. Sociol., 23(3), 181–201.
Freeman, L. C. (1979). “Centrality in social networks conceptual clarification.” Social Networks, 1(3), 215–239.
Genesi, C., Granelli, G., Innorta, M., Marannino, P., Montagna, M., and Zanellini, F. (2007). Identification of critical outages leading to cascading failures in electrical power systems, IEEE, New York.
Guimera, R., Mossa, S., Turtschi, A., and Amaral, L. A. N. (2005). “The worldwide air transportation network: Anomalous centrality, community structure, and cities’ global roles.” Proc. Natl. Acad. Sci. U.S.A., 102(22), 7794–7799.
Lewis, T. G. (2009). Network science: Theory and practice, Wiley, Hoboken, NJ.
Milgram, S. (1967). “The small-world problem.” Psychol. Today, 1(1), 61–67.
Newman, M. E. J. (2003). “The structure and function of complex networks.” SIAM Rev., 45(2), 167–256.
Newman, M. E. J. (2004). “Analysis of weighted networks.” Phys. Rev. E, 70(5), 056131.
Novak, P., Guinot, V., Jeffrey, A., and Reeve, D. E. (2010). Hydraulic modelling—an introduction: Principles, methods and applications, Spon Press, London.
Network Workbench [Computer software]. Indiana Univ., Bloomington, IN; Northeastern Univ., Boston; and Univ. of Michigan, Ann Arbor, MI, 〈http://nwb.slis.indiana.edu〉.
Opsahl, T., Agneessens, F., and Skvorets, J. (2010). “Node centrality in weighted networks: Generalizing degree and shortest paths.” Social Networks, 32(3), 245–251.
O’Rourke, T. D. (2007). “Critical infrastructure, interdependencies, and resilience.” The Bridge, 27–29.
U.S.–Canada Power System Outage Task Force. (2004). Final Rep. on the August 14, 2003 blackout in the United States and Canada: Causes and recommendations, Washington, DC.
U.S. Environmental Protection Agency. (2008). “EPANET.” 〈http://www.epa.gov/nrmrl/wswrd/dw/epanet.html〉 (Jul. 1, 2011).
Watts, D. J., and Strogatz, S. H. (1998). “Collective dynamics of ‘small-world’ networks.” Nature, 393(6684), 440–442.
Information & Authors
Information
Published In
Journal of Infrastructure Systems
Volume 19 • Issue 2 • June 2013
Pages: 157 - 165
Copyright
© 2013 American Society of Civil Engineers.
History
Received: Jul 21, 2011
Accepted: Jul 24, 2012
Published online: Aug 15, 2012
Published in print: Jun 1, 2013
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.