A GRAPH-THEORETIC METHOD FOR ORGANIZING OVERLAPPING CLUSTERS INTO TREES, MULTIPLE TREES, OR EXTENDED TREES

A clustering that consists of a nested set of clusters may be represen ted graphically by a tree. In contrast, a clustering that includes non -nested overlapping clusters (sometimes termed a ''nonhierarchical'' c lustering) cannot be represented by a tree. Graphical representations of such non-nested overlapping clusterings are usually complex and dif ficult to interpret. Carroll and Pruzansky (1975, 1980) suggested repr esenting non-nested clusterings with multiple ultrametric or additive trees. Corter and Tversky (1986) introduced the extended tree (EXTREE) model, which represents a non-nested structure as a tree plus overlap ping clusters that are represented by marked segments in the tree. We show here that the problem of finding a nested (i.e., tree-structured) set of clusters in an overlapping clustering can be reformulated as t he problem of finding a clique in a graph. Thus, clique finding algori thms can be used to identify sets of clusters in the solution that can be represented by trees. This formulation provides a means of automat ically constructing a multiple tree or extended tree representation of any non-nested clustering. The method, called ''clustrees'', is appli ed to several non-nested overlapping clusterings derived using the MAP CLUS program (Arabie and Carroll 1980).