Hierarchical clustering on asymmetric networks

Hierarchical clustering on asymmetric networks - Mémoli

Facundo Mémoli
Ohio State University
November 7, 2015
The problem of determining clusters in a data set admits different interpretations depending on whether the data is metric, symmetric but not necessarily metric, or asymmetric. Whereas there is a good degree of understanding of what are the natural methods for clustering symmetric data, the landscape of methods for clustering asymmetric data is not so well understood. It is possible to study and characterize hierarchical clustering methods that operate on asymmetric networks in an axiomatic manner. In the setting of symmetric data a similar axiomatic leads to a uniqueness theorem, but, in the context of asymmetric data, it turns out that all possible hierarchical clustering methods satisfying these axioms are contained, in an appropriate sense, between two extremal canonical methods. Furthermore, there exist infinite families of methods that mediate between the two extremal methods. We will describe these results and a further classification of these methods based on other properties of practical interest.