Measures of network vulnerability

We propose measures of network vulnerability and study some of their properties. We define a network as a triplet (G, R, F), where G is the graph of the network, R is the routing protocol specifying how traffic flows on G, and F is the traffic load (typically random). Based on this structure, we calculate the expected loss of traffic from an "attack" which eliminates tx 100% of the network's links. The result is a network vulnerability curve (NVC) measuring expected loss as a function of t, 0. <= t <= 1. Clearly, different attack strategies (e.g., random versus malicious) could cause different levels of damages so, accordingly, we define four key NVCs: malicious, greedy, random, and Bernoulli, and study their mathematical properties. Some extensions are discussed.