Excisive Hierarchical Clustering Methods for Network Data
  We introduce two practical properties of hierarchical clustering methods for
(possibly asymmetric) network data: excisiveness and linear scale preservation.
The latter enforces imperviousness to change in units of measure whereas the
former ensures local consistency of the clustering outcome. Algorithmically,
excisiveness implies that we can reduce computational complexity by only
clustering a data subset of interest while theoretically guaranteeing that the
same hierarchical outcome would be observed when clustering the whole dataset.
Moreover, we introduce the concept of representability, i.e. a generative model
for describing clustering methods through the specification of their action on
a collection of networks. We further show that, within a rich set of admissible
methods, requiring representability is equivalent to requiring both
excisiveness and linear scale preservation. Leveraging this equivalence, we
show that all excisive and linear scale preserving methods can be factored into
two steps: a transformation of the weights in the input network followed by the
application of a canonical clustering method. Furthermore, their factorization
can be used to show stability of excisive and linear scale preserving methods
in the sense that a bounded perturbation in the input network entails a bounded
perturbation in the clustering output.
