## 4 Theoretical Motivation of NBR-Clustering
### Computation of NBR Measures  
The existing NP-hardness results for the resilience measures considered in this work include [48] for integrity (Ref. [49] for toughness, Ref. [50] for tenacity, Ref. [51] for scattering number and [52] for conductance). The approximation-hardness of unsmoothened vertex attack tolerance (UVAT) \(\hat{\tau}(G)=\min_{S\subset V}\frac{|S|}{|V-S-C_{max}(V-S)|}\) under four separate, plausible computational complexity assumptions was established in [10; 53]. VAT, integrity, toughness, tenacity and smoothed inverse scattering number are all minimization problems, whose objective functions involve similar calculations of component orders and numbers. Based on the approximation hardness of UVAT, the conjectured hardness of VAT and the previous NP-hardness results for the resilience measures, a greedy betweenness centrality (BC) based algorithm that is similar to the implementation of VAT-Clust presented in [6], was used to calculate the resilience measures. This greedy BC based heuristic algorithm is detailed in [10] and referred to as Greedy-BC.  
The Greedy-BC algorithm takes graph \(G=(V,E)\) and set-resilience measure function \(R\) as input. Let \(n\) denote the total number of nodes in \(G\). The Greedy-BC algorithm is as follows:  
1. Initialize \(G_{0}=G\), \(S_{0}=\emptyset\), \(r_{j}=\infty\), \(r^{min}=\infty\), and \(S^{min}=\emptyset\).
2. For \(j:=1\) to \(n\) do: 1. \(u_{j}=\max_{u\in V(G_{j-1})}BC(u)\), 2. \(S_{j}=S_{j-1}\cup\{u_{j}\}\), and \(r_{j}=R(G,S_{j})\), 3. If \(r_{j}<r^{min}\), then assign \(r^{min}=r_{j}\), and \(S^{min}=S_{j}\), 4. \(G_{j}=G_{j-1}-\{u_{j}\}\).
3. Output \(S^{min}\) as the critical attack set achieving minimum resilience, and \(r^{min}\) as the minimum value achieved for the resilience measure \(R\).  
The overall time complexity of the Greedy-BC algorithm depends on the algorithm used to determine the node with the highest BC in each iteration. In general, if that algorithm takes time \(O(B)\), then the overall time complexity of Greedy-BC may be expressed as \(O(|V|(B+|E|))\). If restricted to exact, deterministic, sequential computational models, the fastest known algorithm to determine the node with the highest BC is [PERSON]'s Fast Betweenness Centrality algorithm [54], which takes \(O(|V||E|)\) time, yielding an overall Greedy-BC time complexity of \(O(|V|^{2}|E|)\). As in [10], in the context of the work, we implemented Greedy-BC using [PERSON]'s algorithm [54] and applied it to all graphs of size up to two thousand vertices. (for graphs with over two thousand vertices, we use a distributed algorithm [55]).  
In [10], it is experimentally shown that Greedy-BC implemented using [PERSON] betweenness centrality algorithm exhibits excellent empirical approximation bounds for VAT, integrity and tenacity on a representative sample of 24-node graphs, despite the general approximation hardness results for UVAT. In [6], hill climbing was applied to improve the approximation of the resilience measures; however, it is shown in [10] that the accuracies of Greedy-BC were not significantly improved by either 1D or 2D hill climbing, even for larger scale-free graphs up to thousands of nodes. The non-parametrized, practical NBR-Clust implementation employed in this work uses Greedy-BC without hill climbing and with unweighted betweenness centrality to _simultaneously_ approximate VAT, integrity, tenacity, toughness, and scattering in \(O(|V|^{2}|E|)\) time.  
While Greedy-BC as implemented above yields high clustering accuracy for all graphs studied as well as an improvement in speed over hill-climbing based methods, it is still too slow for applications to very large graphs of tens or hundreds of thousands of nodes. Therefore, we have considered alternative approaches to tackle very large graphs, including parallelized approximations to betweenness centrality [55] and the use of adaptive approximations [56].