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:
- Quasi-Equivalence Relations: Unlike standard equivalence, these are reflexive and transitive but not necessarily symmetric, allowing for a partial order of influence.
- Quasi-Dendrograms: These represent nested collections of quasi-partitions, often visualized as Directed Acyclic Graphs (DAGs) showing unidirectional influence.
- 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.
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.
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