Measuring graph robustness
There are a couple ways to measure how well a graph remains connected when nodes are removed. One ways is to consider nodes dropping out randomly. Another way, the one we look at here, assumes an adversary is trying to remove the most well-connected nodes. This approach was defined by Schneider et al [1]. It is also described, a little more clearly, in [2].
The robustness of a graph is defined as
Then [2] explains that
N is the total number of nodes in the initial network and S(q) is the relative size of the largest connected component after removing q nodes with the highest degrees. The normalization factor 1/N ensures 1/N a R a 0.5. Two special cases exist: R = 1/N corresponds to star-like networks while R = 0.5 represents the case of the fully connected network.
Apparently "relative size" means relative to the size of the original network, not to the network with q nodes removed.
There is one difference between [1] and [2]. The former defines the sum up to N and the latter to N-1. But this doesn't matter because S(N) = 0: when you remove N nodes from a graph with N nodes, there's nothing left!
I have a couple reservations. One is that it's not clear whether R is well defined.
Consider the phrase "removing q nodes with the highest degrees." What if you have a choice of nodes with the highest degree? Maybe all nodes have degree no more than n and several have degree exactly n. It seems your choice of node to remove matters. Removing one node of degree n may give you a very different network than removing another node of the same degree.
Along the same lines, it's not clear whether it matters how one removes more than one degree. For S(2), for example, does it matter whether I remove the two most connected nodes from the original graph at once, or remove the most connected node first, then the most connected node from what remains?
My second reservation is that I don't think the formula above gives exactly the extreme values it says. Start with a star graph. Once you remove the center node, there are only isolated points left, and each point is 1/N of the original graph. So all the S(q) are equal to 1/N. Then R equals (N - 1)/ N2, which is less than 1/N.
With the complete graph, removing a point leaves a complete graph of lower order. So S(q) = (N - q)/N. Then R equals (N - 1)/2N, which is less than 1/2.
* * *
[1] CM Schneider et al, Mitigation of malicious attacks on networks. P. Natl. Acad. March 8, 2011, vol. 108. no. 10
[2] Big Data of Complex Networks, CRC Press. Matthias Dehmer et al editors.