Hierarchical Quasi-Clustering Methods for Asymmetric Networks

Gunnar E. Carlsson, Facundo Mémoli, Alejandro Ribeiro, Santiago Segarra

Introduction

Standard hierarchical clustering typically forces asymmetric data into symmetric dendrograms, a process that often destroys the directional "influence" inherent in many real-world networks. Whether analyzing migration patterns (e.g., movement from New York to Florida) or economic flows between sectors, the relationship between nodes is rarely reciprocal. This paper introduces quasi-clustering, a mathematical framework that preserves this asymmetry through "quasi-dendrograms." The authors demonstrate that a directed version of single linkage is the unique, mathematically sound method for this task.

Methodology: From Dendrograms to Quasi-Dendrograms

The core challenge in clustering asymmetric data is the "symmetrization mismatch," where directional information is lost by averaging weights before analysis. To solve this, the authors propose several key mathematical constructs:

  1. Quasi-Equivalence Relations: Unlike standard equivalence, these are reflexive and transitive but not necessarily symmetric, allowing for a partial order of influence.
  2. Quasi-Dendrograms: These represent nested collections of quasi-partitions, often visualized as Directed Acyclic Graphs (DAGs) showing unidirectional influence.
  3. Directed Single Linkage (DSL): This algorithm identifies the "minimum chain cost"—the path with the smallest maximum-weight edge—between nodes to determine cluster membership and directionality.
Figure 4: Comparison of an asymmetric network (top left), its standard symmetric dendrogram (top right), and the resulting quasi-dendrogram evolution across different thresholds of δ (bottom).

The authors prove that DSL is the only method satisfying two fundamental "admissibility" axioms: Value and Transformation. Furthermore, by utilizing dioid algebra (min-max matrix powers), the DSL output can be computed with a complexity of approximately $O(n^{2.7})$, making it practical for networks with thousands of nodes.

Key Results and Applications

The utility of quasi-clustering was tested on two primary datasets: US Internal Migration (2011) and US Economic Input-Output (2011).

Migration Analysis

In the study of US migration, DSL successfully identified California as a dominant "source" of migration for the Western United States. Unlike symmetric methods that simply group these states together, quasi-clustering revealed a clear hierarchy: California influences Oregon and Washington, which subsequently influence Nevada.

Figure 6: Progression of the migration quasi-dendrogram for the Western US. As δ increases, states are absorbed into the influential cluster led by California.

Economic Influence

Analysis of the 14-sector US economic model highlighted 'Professional Services' and 'Manufacturing' as the primary drivers of the economy. The method specifically showed that Manufacturing's influence is concentrated on primary sectors like Agriculture and Mining, while Professional Services drive tertiary sectors like Finance.

Discussion and Future Directions

Quasi-clustering provides a stable framework—small changes in input data result in only minor changes to the output. However, like its symmetric counterpart, Directed Single Linkage is susceptible to the "chaining effect," where intermediate points can cause distinct clusters to merge prematurely. Future research may explore density-aware asymmetric methods or faster approximations to scale the $O(n^{2.7})$ complexity for massive, web-scale graphs. By preserving the "order of influence," quasi-clustering offers a more nuanced lens for understanding the directional dynamics of complex networks.

Summary updated

Abstract

This paper introduces hierarchical quasi-clustering methods, a generalization of hierarchical clustering for asymmetric networks where the output structure preserves the asymmetry of the input data. We show that this output structure is equivalent to a finite quasi-ultrametric space and study admissibility with respect to two desirable properties. We prove that a modified version of single linkage is the only admissible quasi-clustering method. Moreover, we show stability of the proposed method and we establish invariance properties fulfilled by it. Algorithms are further developed and the value of quasi-clustering analysis is illustrated with a study of internal migration within United States.
BibTeX
@inproceedings{carlsson2014hierarchical,
  author = {Gunnar E. Carlsson and Facundo Mémoli and Alejandro Ribeiro and Santiago Segarra},
  title = {{Hierarchical Quasi-Clustering Methods for Asymmetric Networks}},
  booktitle = {International Conference on Machine Learning},
  year = {2014},
  url = {https://openreview.net/forum?id=H1ZYDhZO-r},
}
Figure