SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES

This paper selectively reviews some of the recent developments in sequencing objects along a continuum that rely upon a symmetric proximity measure defined between the objects to be seriated and emphasizes the notion of a maximal spanning tree and related ‘crude’ seriation strategies that require only the ordinal information from the basic proximity values.

Abstract

This paper selectively reviews some of the recent developments in sequencing objects along a continuum that rely upon a symmetric proximity measure defined between the objects to be seriated. Most of the discussion is from a graph‐theoretical point of view and emphasizes the notion of a maximal spanning tree and related ‘crude’ seriation strategies that require only the ordinal information from the basic proximity values. In addition, correspondences with several hierarchical clustering techniques are presented as well as an extension to the newer circular‐arc models developed in mathematics. A number of substantive examples are given incorporating data sets available in the psychological literature that have been analysed previously with alternative methods.