## 3 NBR Measures in Clustering  
### Definitions of Node Resilience Measures  
Resilience measures attempt to quantify the cost of an attack on a network in proportion to the amount of disruption the attack causes. A common measure of cost is the size of the critical attack set. The attack set is defined as a set of nodes whose removal causes disruption to a network, dividing it into disconnected components. An attack set can also be referred to as a node-cut, a cut set or a separator. The disruption created by the removal of an attack set must also be quantified. Common ways of quantifying disruption include the number of resulting components (the higher the value, the greater the disruption) or the size of the largest remaining connected component (the lower the value, the greater the disruption). For comparisons of various resilience or vulnerability measures, including those involved in this work, we refer the reader to [10]. An observation one may make about all of these NBR measures is that they return critical attack sets likely to consist of inter-cluster boundary nodes, bridge nodes and bottlenecks. The components created by removing the critical attack set are employed as the basis for candidate clusters. Given an undirected connected graph \(G=(V,E)\), the NBR measures used in this work are as follows:  
VAT [7; 8] is defined as  
\[\tau(G)=\min_{S\subset V}\left\{\frac{|S|}{|V-S-C_{max}(V-S)|+1}\right\}, \tag{1}\]  
where \(S\) is an attack set and \(C_{max}(V-S)\) is the largest connected component in \(V-S\). Vertical bars in the notation represent the cardinality of a set, such that \(|S|\), for example, represents the cardinality of the set \(S\). Normalized integrity [11] is defined as  
\[I(G)=\min_{S\subset V}\left\{\frac{|S|+|C_{max}(V-S)|}{|V|}\right\}. \tag{2}\]  
Toughness [12] is defined as  
\[t(G)=\min_{S\subset V}\left\{\frac{|S|}{\omega(V-S)}\right\}, \tag{3}\]  
where \(\omega(V-S)\) is the number of connected components in \(V-S\). Tenacity [13] is defined as  
\[T(G)=\min_{S\subset V}\left\{\frac{|S|+|C_{max}(V-S)|}{\omega(V-S)}\right\}. \tag{4}\]  
Inverse scattering number [14] is defined as  
\[h(G)=\min_{S\subset V}\left\{\frac{1}{\omega(V-S)-|S|}\right\}. \tag{5}\]  
This paper compares results using the above five resilience measures to the popular _spectral clustering_ and _Louvain_ methods. Spectral clustering uses combinatorial conductance, and Louvain is based on a measure called modularity. For completeness, combinatorial conductance and modularity are defined below. Combinatorial conductance or edge based conductance [5; 38] is defined as  
\[\Phi(G) =\min_{S\subset V,Vol(S)\leq Vol(V)/2}\left\{\frac{|Cut(S,V-S)|} {Vol(S)}\right\}\] \[=\min_{S\subset V,Vol(S)\leq Vol(V)/2}\left\{\frac{|Cut(S,V-S)|} {\delta_{S}|S|}\right\},\]  
where \(|Cut(S,V-S)|\) is the size of the cut separating \(S\) from \(V-S\), \(Vol(S)\) is the sum of the degrees of vertices in \(S\), and \(\delta_{S}\) is the _average_ degree of vertices in \(S\). Modularity is a way of measuring the goodness of a partitioning of a graph. It is defined as  
\[Modularity(G)=\sum_{P=1}^{n_{P}}\left[\frac{m_{i}}{m}-\frac{(2m_{i}+m_{e})^{2}}{ 4m^{2}}\right], \tag{6}\]  
where \(P_{1},..,P_{n_{P}}\) are components of a partitioning, \(m=|E|\), \(m_{i}=|\{(u,v)\in E:u\in P_{i},v\in P_{i}\}|\), and \(m_{e}=|\{(u,v)\in E:u\in P_{i},v\
otin P_{i}\}|\). Other important graph measures exist which could be used within the NBR-Clust framework. Although we do not use it here, one such example is _entropy_[39], which could be used to rank the importance of nodes as in [40]. An example of the effectiveness of multiple NBR measures to cluster a simple graph is illustrated in Figure 1. For each graph, the white nodes denote the attack set returned by the corresponding resilience measure. For example, in Figure 1a, the attack set returned by VAT is the center node. Removing this node creates six disconnected clusters, the smallest of which is one node and the largest of which is eight nodes.