Dendrogram Seriation Using Simulated Annealing

Abstract

Seriation is the ordering of the leaves of a dendrogram, such that leaves representing similar items are placed near each other according to some metric, within the constraints of the cluster tree. Such ordering greatly aids the interpretation of the relations represented by the dendrogram and reduces visual misinterpretation caused by unrelated items from different sub-trees being placed near each other during random ordering. The seriation method presented here uses simulated annealing to find an approximately optimal dendrogram ordering by minimizing a penalty function. The method employs a ‘similarity weighted distance’ penalty function that tends to avoid artifacts introduced by the traveling salesman problem algorithms commonly used for dendrogram seriation. Examples are given showing the effectiveness of the method in presenting dendrograms of the structure of a social network, and additional examples show an application for interpreting the structure of a network of journal papers covering the subject of anthrax research.