Constructing optimal ultrametrics

Abstract

Clique optimization (CLOPT) is a family of graph clustering procedures that construct parsimonious ultrametrics by executing a sequence of divisive and agglomerative operations. Every CLOPT procedure is associated with a distinct graph-partitioning heuristic. Seven HCS methods, a mathematical programming algorithm, and two CLOPT heuristics were evaluated on simulated data. These data were obtained by distorting ultrametric partitions and hierarchies. In general, internally optimal models yielded externally optimal models. By recovering near-optimal solutions more consistently, CLOPT2 emerged as the most robust technique. © 1993 Springer-Verlag New York Inc.