Hierarchical clustering on asymmetric networks
Presenter
November 7, 2015
Keywords:
- Workshop on Topology: Identifying Order in Complex Systems
Abstract
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.