Robust Hierarchical Clustering for Directed Networks: An Axiomatic
  Approach
  We provide a complete taxonomic characterization of robust hierarchical
clustering methods for directed networks following an axiomatic approach. We
begin by introducing three practical properties associated with the notion of
robustness in hierarchical clustering: linear scale preservation, stability,
and excisiveness. Linear scale preservation enforces imperviousness to change
in units of measure whereas stability ensures that a bounded perturbation in
the input network entails a bounded perturbation in the clustering output.
Excisiveness refers to the local consistency of the clustering outcome.
Algorithmically, excisiveness implies that we can reduce computational
complexity by only clustering a subset of our data while theoretically
guaranteeing that the same hierarchical outcome would be observed when
clustering the whole dataset. In parallel to these three properties, we
introduce the concept of representability, a generative model for describing
clustering methods through the specification of their action on a collection of
networks. Our main result is to leverage this generative model to give a
precise characterization of all robust -- i.e., excisive, linear scale
preserving, and stable -- hierarchical clustering methods for directed
networks. We also address the implementation of our methods and describe an
application to real data.
