## 4 Theoretical Motivation of NBR-Clustering  
Although the bulk of results in this work are empirical, our original motivation for considering node-based resilience measures for the clustering problem is theoretical. We first observe that, in well-known clustering algorithms, including sparsest-cuts [3], spectral clustering [4], and conductance [5], an edge-based resilience problem is solved such that the components resulting from the removal of the critical edge-cutset is output as candidate clusters. Then, we ask what would be the efficacy and special properties of a clustering algorithm founded upon _node_-based resilience measures instead. Towards exploring this question, we must naturally examine both (i) the relationship between edge-based resilience and node-based resilience as well as (ii) the fundamental differences between them. Due to the classical importance of conductance-based clustering methods, intimately related to both sparsest-cuts and spectral clustering due to Cheeger's inequality, as well as the mathematical significance of conductance in general, we first take conductance to be a representative edge-based resilience measure. In recent work [10], VAT was noted to exhibit desirable characteristics compared to a host of other node-based resilience measures considered. As such, towards exploring item (i), we observe the following bounds proven in [8; 9; 10] relating VAT to both conductance and spectral gap for the case of regular degree graphs, hinting at some similarity in expected results between VAT-based clustering and spectral clustering for constant-degree almost-regular graphs: For any \(d\)-regular connected graph \(G=(V,E)\) with \(\lambda_{2}\) denoting the second largest eigenvalue of \(G\)'s normalized adjacency matrix and \(\Phi(G)\) denoting the conductance of \(G\),  
\[\frac{1}{d}\Phi(G)\leq\tau(G)\leq d^{2}\Phi(G). \tag{7}\]  
Moreover,  
\[\frac{\tau(G)^{2}}{2d^{4}}\leq 1-\lambda_{2}\leq 2d\tau(G). \tag{8}\]  
While seminal graph families such as Erdos-Renyi graphs do indeed have almost-regular degree distributions in expectation, a preponderance of real data suggest highly scale-free or generally irregular degree distributions for many complex networks. On such highly variant degree distributions significant discrepancies between edge-based resilience and node-based resilience may be exhibited: As shown in [10], extremal discrepancy between node-based resilience measures and edge-based resilience measures arises in the star family of graphs, which have maximal conductance but minimal VAT. While the applicability of the star graphs in clustering problems may be suspect, two generalizations of the star family into star-of-cliques and the hypergraph \(Kstar-r-uniform\) are indeed relevant for clustering. We now examine the behavior of node-based resilience measures versus edge-based resilience measures on these relevant generalizations. As in preliminary work [15], consider the star-of-cliques graph family \(K_{\beta}-Star(\alpha)=(V,E)\) with \(n=|V|=\alpha\beta+1\) constructed by connecting one central node \(v_{c}\) to each of \(j=1,\ldots,\alpha\) disjoint \(\beta\)-cliques \(K_{\beta}^{j}\) via \(\alpha\) edges of the form \(\{v_{c},v_{j}\}\). In particular, for each clique \(K_{\beta}^{j}\), there is a unique vertex \(v_{j}\) that is adjacent to the central vertex \(v_{c}\), and we may refer to the set of \(\alpha\) vertices adjacent to \(v_{c}\) as \(V_{adj}\). An example graph with \(\alpha=\beta=5\) is shown in Figure 2. Any reasonable NBR measure for this graph, including all measures considered herein, will output either \(\{v_{c}\}\) or \(V_{adj}\) as the critical attack set \(S\subset V\) optimizing the NBR measure. As such, the removal of the critical attack set of a node-based resilience measure will result in either exactly \(\alpha\) components corresponding identically to the \(\alpha\) cliques \(K_{\beta}\) or it will result in exactly \(\alpha+1\) components which include the central node and \(\alpha\) cliques \(K_{\beta-1}\).