A common theme in analysis and evaluation of network-based critical infrastructure is the assessment of system vulnerability. Graph theoretic, simulation, and optimization-based techniques have played a significant role in examining potential network vulnerabilities given the insights they can provide for mitigating facility loss and prioritizing fortification efforts. Central to these approaches is the concept of facility (arc—node) importance or criticality to system survivability. Assessments of network vulnerability can dramatically differ based on how facility importance is characterized. In this review, various approaches for assessing facility importance and network vulnerability are examined. The key differences in these approaches are the ways in which a facility's role in maintaining network operability is evaluated given arc—node disruption. Comparative results suggest significant differences exist among measures of facility importance and network performance. Furthermore, the subsequent incongruities in these measures and their implications need to be clearly understood to support interdiction risk and vulnerability assessment for critical infrastructures.
Abilene.2005. About Abilene . http://abilene.internet2.edu/about/.
2.
Albert, R., I. Albert, and G.L. Nakarado.2004. Structural vulnerability of the North American power grid. Physical Review E69: 1—4.
3.
Albert, R., H. Jeong, and A.-L. Barabasi.2000. Error and attack tolerance of complex networks. Nature406: 378—82.
4.
Alderson, D., L. Li, W. Willinger, and J.C. Doyle.2005. Understanding Internet topology: Principles, models and validation. IEEE/ACM Transactions on Networking13: 1205—18.
5.
Alevras, D., M. Grotschel, and R. Wessaly.1997. Capacity and survivability models for telecommunication networks. In Proceedings of the Euro/Informs Meetings, 187—99. Barcelona, Spain: Euro/Informs .
6.
Ball, M.O., B.L. Golden, and R.V. Vohra.1989. Finding the most vital arcs in a network . Operations Research Letters8: 73—76.
7.
Barabasi, A.L.2003. Linked: The new science of networks. Cambridge, MA: Pegasus.
8.
Barabasi, A.L., and R. Albert.1999. Emergence of scaling in random networks . Science286: 509.
9.
Barabasi, A.-L., E. Ravasz, and T. Vicsek.2001. Deterministic scale-free networks. Physica A: Statistical Mechanics and Its Applications299 (3—4): 559—64.
10.
Carreras, B.A., V.E. Lynch, I. Dobson, and D.E. Newman.2002. Critical points and transitions in an electric power transmission model for cascading failure blackouts. Chaos12: 985—94.
11.
Chung, S.-H., Y.-S. Myung, and S.-W. Tcha.1992. Optimal design of a distributed network with a two-level hierarchical structure. EuropeanJournal of Operational Research62: 105—15.
12.
Church, R.L., and M.P. Scaparra.2007a. Analysis of facility systems' reliability when subject to attack or natural disaster. In Critical infrastructure: Reliability and vulnerability, ed. A. T. Murray and T. H. Grubesic, 221—42. Berlin, Germany: Springer Verlag.
13.
Church, R.L., and M.P. Scaparra.2007b. Protecting critical assets: The r-interdiction median problem with fortification. Geographical Analysis39: 129—46.
14.
Church, R.L., M.P. Scaparra, and R.S. Middleton.2004. The median and covering facility interdiction problems. Annals of the Association of American Geographers94: 491—502.
15.
Cohen, R., K. Erez, D. ben-Avraham, and S. Havlin.2000. Resilience of the Internet to random breakdowns. Physical Review Letters85: 4626—28.
16.
Corley, H.W., and H. Chang.1974. Finding the n most vital nodes in a flow network. Management Science21: 362—64.
17.
Corley, H.W., and D.Y. Sha.1982. Most vital links and nodes in weighted networks. Operations Research Letters1: 157—60.
18.
Costa, L.F.2004. Reinforcing the resilience of complex networks . Physical Review E69: 066127.
19.
Crucitti, P., V. Latora, and M. Marchiori.2004a. Model for cascading failures in complex networks. Physical Review E69: 045104(R).
20.
Crucitti, P., V. Latora, and M. Marchiori.2004b. A topological analysis of the Italian electric power grid. Physica A338: 92—97.
21.
Crucitti, P., V. Latora, M. Marchiori, and A. Rapisarda.2004. Error and attack tolerance of complex networks. Physica A340: 388—94.
22.
Curran, K., D. Woods, N. McDermot, and C. Bradley.2003. The effects of badly behaved routers on Internet congestion. International Journal of Network Management13: 83—94.
23.
Doyle, J.C., D.L. Alderson, L. Li, S. Low, M. Roughan, S. Shalunov, R. Tanaka, and W. Willinger.2005. The ``robust yet fragile'' nature of the Internet. Proceedings of the National Academy of Sciences. http://www.pnas.org/cgi/doi/10.1073/pnas.0501426102 .
24.
Freeman, L.C.1977. A set of measures of centrality based on betweenness . Sociometry40: 35—41.
25.
Freeman, L.C.1979. Centrality in social networks: I. Conceptual clarification . Social Networks1: 215—39.
26.
Fulkerson, D.R., and G.C. Harding.1977. Maximizing the minimum source-sink path subject to a budget constraint. MathProgram13: 116—18.
27.
Garrison, W.L., and D.F. Marble.1962. Graph theoretic concepts. In Transportation geography: Comments and readings, ed. M. E. Eliot Hurst, 73—88. New York: McGraw-Hill.
28.
Golden, B.L.1978. A problem in network interdiction. Naval Research Logistics Quarterly25: 711—13.
29.
Grubesic, T.H., and A.T. Murray.2006. Vital nodes, interconnected infrastructures and the geographies of network survivability. Annals of the Association of American Geographer96: 64—83.
30.
Grubesic, T.H., A.T. Murray, and J. Mefford.2007. Continuity in critical infrastructure: Accounting for nodal disruptions. In Critical infrastructure: Reliability and vulnerability, ed. A. T. Murray and T. H. Grubesic, 197—220. Berlin, Germany: Springer Verlag.
31.
Grubesic, T.H., M.E. O'Kelly, and A.T. Murray.2003. A geographic perspective on commercial Internet survivability. Telematics and Informatics20: 51—69.
32.
Haggett, P., and R.J. Corley.1969. Network analysis in geography. New York: St. Martin's.
33.
Ham, H., T.J. Kim, and D.E. Boyce.2005. Assessment of economic impacts from unexpected events using an interregional commodity flow and network model . Transportation Research Part A39: 849—60.
34.
Harary, F., R.Z. Norman, and D. Cartwright.1965. Structural models. New York: John Wiley.
35.
Holme, P., J.K. Beom, C.N. Yoon, and S.K. Han.2002. Attack vulnerability of complex networks . Physical Review E65: 056109.
36.
Israeli, E., and R.K. Wood.2002. Shortest-path network interdiction . Networks40: 97—111.
37.
Kim, T.J., H. Ham, and D.E. Boyce.2002. Economic impacts of transportation network changes: Implementation of a combined transportation network and input-output model. Papers in Regional Science81: 223—46.
38.
Latora, V., and M. Marchiori.2005. Vulnerability and protection of infrastructure networks. Physical Review E71: 015103(R).
39.
Malik, K., A.K. Mittal, and S.K. Gupta.1989. The most vital arcs in the shortest path problem. Operations Research Letters8: 223—27.
40.
Matisziw, T.C., A.T. Murray, and T.H. Grubesic.2007. Bounding network attack vulnerability through cutset identification. In Critical infrastructure: Reliability and vulnerability , ed. A. T. Murray and T. H. Grubesic, 243—56. Berlin, Germany: Springer Verlag.
41.
McMasters, A.W., and T.M. Mustin.1970. Optimal interdiction of a supply network . Naval Research Logistics Quarterly17: 261—68.
42.
Murnion, S., and R.G. Healey.1998. Modelling distance decay effects in Web server information flows. Geographical Analysis30: 285—303.
43.
Murray, A. T., and T. H. Grubesic, eds. 2007. Critical infrastructure: Reliability and vulnerability. Berlin, Germany: Springer Verlag.
44.
Murray, A.T., T.C. Matisziw, and T.H. Grubesic.2007. Critical network infrastructure analysis: Interdiction and system flow. Journal of Geographical Systems9: 103—17.
45.
Myung, Y.-S., and H.-J. Kim.2004. A cutting plane algorithm for computing k-edge survivability of a network. EuropeanJournal of Operational Research156: 579—89.
46.
Newman, M.E.J.2003. The structure and function of complex networks . SIAM Review45: 167—256.
47.
O'Kelly, M.E., and T.H. Grubesic.2002. Backbone topology, access and the commercial Internet. Environment and Planning B 29: 533—52.
48.
O'Kelly, M.E., H. Kim, and C. Kim.2006. Internet reliability with realistic peering. Environment and Planning B 33: 325—43.
49.
Parthasarathy, K.R.1964. Enumeration of paths in digraphs. Psychometrika29: 153—65.
50.
Ratliff, H.D., G.T. Sicilia, and S.H. Lubore.1975. Finding the n most vital links in flow networks. Management Science2: 531—39.
51.
Shimbel, A.1953. Structural properties of communication networks. Bulletin of MathematicalBiophysics15: 501—7.
52.
Tanizawa, T., G. Paul, R. Cohen, S. Havlin, and H.E. Stanley.2005. Optimization of network robustness to waves of targeted and random attacks. Physical Review E 71: 047101.
53.
Thadakamalla, H.P., U.N. Raghavan, S. Kumara, and R. Albert.2004. Survivability of multiagentbased supply networks: A topological perspective. IEEE IntelligentSystems19: 24—31.
54.
Watts, D.J.1999. Small worlds: The dynamics of networks between order and randomness. Princeton, NJ: Princeton University Press.
55.
Watts, D.J., and S. Strogatz.1998. Collective dynamics of small world networks . Nature393: 440—42.
56.
White House.2003. The national strategy for the physical protection of critical infrastructures and key assets. http://www.whitehouse.gov/pcipb/physical_strategy.pdf .
57.
Wollmer, R.1964. Removing arcs from a network. Operations Research12: 934—40.
58.
Wollmer, R.1970. Algorithms for targeting strikes in a lines-of-communication network. Operations Research18: 497—515.
