Matrix reordering algorithms

Question

I have a similarity matrix and I would like to apply an algorithm that reorders the entries based on their similarity. The aim is to move entries with high similarity closer to the main diagonal. The optimal configuration would be sub-blocks / clusters of similar entries along the main diagonal. Ideas anyone?

Answer 1

Use hierarchical clustering, in particular single linkage clustering.

Not so much because of the clustering, but because this groups objects by similaritiy. In your case, it would first place the two most similar rows next to each other. Then the second two most similar. And so on.

This is a quite common in visualizing bioinformatics; it is usually used to reorder both columns and rows independently (e.g. rows = genes, columns = experiments -- neither of which has a naturally meaningful order). But if you only have a similarity matrix, you can also use it to reorder columns=rows at the same time.

Answer 2

The goal of this question should be a blocking algorithm for the similarity matrix. I propose a solution based on hierarchical clustering followed by a sorting of columns based on the clusters.

I assume the author of the question has a matrix containing similarity values between the items, ordered in columns and rows.

To order the columns:

1. Calculate the similarity between the columns of the matrix. For doing so, you can use the cosine similarity. Now you have a list with similarity for every combination of rows/columns, which has to be sorted. Highest values suggest a high similarity between columns. And columns with high similarity should be places close together in the final representation.
2. Build clusters based on the similarity of columns. For example start with pair with highest similarity. This is your first cluster. Take the next pair. Check if there is already a cluster containing one entry of the pair. If there is one add it to that cluster or combine clusters if columns are in different clusters, otherwise it is a new cluster. Proceed until you reach an arbitrarily chosen threshold in similarity. Finally, you have the clusters.
3. reorder the columns so that clusters are close neighboring columns. Don't forget to reorder the rows, two.

The first time I solved this problem I started with the paper with DOI: 10.1109/TKDE.2010.271