Stochastics and StatisticsAn experimental comparison of seriation methods for one-mode two-way data

- Seriation criteria for one-mode two-way data fall into three distinct groups.
- Extensive experiments with different criteria and seriation methods are performed.
- Spectral seriation and multidimensional scaling provide a good quality/speed tradeoff.
- Researchers can conduct their own experiments using the R package seriation.

Seriation aims at finding a linear order for a set of objects to reveal structural information which can be used for deriving data-driven decisions. It presents a difficult combinatorial optimization problem with its roots and applications in many fields including operations research. This paper focuses on a popular seriation problem which tries to find an order for a single set of objects that optimizes a given seriation criterion defined on one-mode two-way data, i.e., an object-by-object dissimilarity matrix. Over the years, members of different research communities have introduced many criteria and seriation methods for this problem. It is often not clear how different seriation criteria and methods relate to each other and which criterion or seriation method to use for a given application. These methods are representing tools for analytics and therefore are of theoretical and practical interest to the operations research community. The purpose of this paper is to provide a consistent overview of the most popular criteria and seriation methods and to present a comprehensive experimental study to compare their performance using artificial and a representative set of real-world datasets.