## 4 Theoretical Motivation of NBR-Clustering
In other words, the computation of a node-based resilience measure results in the immediate partitioning of the star-of-cliques such that every clique corresponds to a distinct cluster, either in its entirety or with only a single node removed. On the other hand, when considering the conductance of this same star-of-cliques family, it may be observed that, for any setting of \(\alpha,\beta>1\), there are several ties for the critical attack set of edges corresponding to conductance: in fact, conductance is minimized by _any_ edge-cutset \(H\) that is a subset of \(E_{c}=\{\{v_{c},v_{j}\}|v_{j}\in V_{adj}\}\) and hence cannot adequately cluster this graph. The behavior of modularity is dependent on the parameters \(\alpha\) and \(\beta\), where there exist settings of those parameters such that modularity will group some of the cliques together into a cluster. For example, if one takes \(\alpha=1024\) and \(\beta=4\), then the modularity objective function will result in fewer than 1020 clusters. Therefore, while NBR-measures yield the natural clusters for the star-of-cliques graphs regardless of \(\alpha\) and \(\beta\), edge-based resilience measures do not. In addition, we shall now demonstrate that this is also the case for the graph representation of the \(Kstar-r-uniform\) hypergraph [41] with respect to the graph representation mapping hyperedges to cliques [42]. As defined in [41], the _star hypergraph_ has center node \(v_{c}\) and is formed by some number of hyperedges containing vertex \(v_{c}\). When the number of vertices involved in every hyperedge of the star hypergraph is the same number \(r\), then we obtain the \(KStar-r-uniform\) hypergraph. For consistency of notation here, we may refer to the graph representation of the \(KStar-r-uniform\) hypergraph with \(\alpha\) hyperedges and \(\beta=r\) simply as the graph \(KStar(\alpha,\beta)\). Note that like \(K_{\beta}-Star(\alpha)\), \(KStar(\alpha,\beta)\) also involves a central node \(v_{c}\) connected to \(\alpha\) cliques \(K_{\beta}\). However, unlike the star-of-cliques graphs where \(v_{c}\) is connected to each clique \(K_{\beta}^{j}\) via a single connection \(v_{j}\in V_{adj}\), in the \(KStar(\alpha,\beta)\) graphs the central node \(v_{c}\) is connected to _all other nodes_. Thus, any vertex separator \(S\) for \(KStar(\alpha,\beta)\) must include \(v_{c}\) and is not improved by additional nodes. Therefore, it is straightforward to see that all node-based resilience measures will output only \(v_{c}\) as the critical attack set for \(KStar(\alpha,\beta)\). We may also observe that the conductance of \(KStar(\alpha,\beta)\) suffers a similar problem as the conductance of \(K_{\beta}-Star(\alpha)\), as there are several ties for the critical attack set of edges corresponding to conductance: Letting \(E_{j}\) denote all the edges connecting \(v_{c}\) to clique \(K_{\beta}^{j}\), for any \(K\subset\{1,2,\ldots\alpha\}\), conductance is minimized by edge-cutset \(H=\bigwedge_{i\in K}E_{i}\). Hence, conductance cannot adequately cluster \(KStar(\alpha,\beta)\). Finally, regarding the behavior of modularity on \(KStar(\alpha,\beta)\), we again note the dependence on \(\alpha\) and \(\beta\), as well as the specific case \(\beta=4\), \(\alpha=1024\) providing a counter-example to the efficacy of modularity in detecting all of the clusters, which are naturally the cliques representing the hyperedges. Therefore, we have exhibited classes of graphs for which NBR-measures output all of the natural clusters although some well-known clustering algorithms based on conductance or modularity may fail to do so. As no clustering algorithm is expected to work perfectly in all scenarios, this is neither a criticism of established clustering methods nor a zealous celebration of the NBR-clustering framework presented herein. Nor have we attempted to exhaustively examine graph families for which NBR-Clust has special positive clustering properties. Rather, we simply solidify our theoretical motivation for the NBR-Clustering framework.