# How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

I have the following code which takes a DataFrame and plot the pdist matrix.

from scipy.spatial.distance import squareform, pdist
res = pdist(df, 'euclidean')
df1 = pd.DataFrame(squareform(res), index=df.index, columns= df.index)
plt.imshow(df1)


I would like to reorder the columns such that the adjacency matrix will cluster together rows/columns with higher interactions. To make it look something like this:

As far as I understand, you are looking for a family of algorithms that are used to reorder sparse matrices. Usually, it is used to reduce fill-in during sparse factorization; however, it's certainly not the only use.

The first candidate would be (reverse) Cuthill-McKee algorithm. Also, take a look at Matlab sparse matrix reordering page that would demonstrate the work of "column-count" and "minimum degree reorderings". Many others exist. Also, this question on SciComp might be useful. The particular choice of strategy will depend on its intended use and requirements on the reordering phase heaviness.

Notice, that the picture you've shown as an example is produced by sorting the adjacency matrix using additional information about the matrix entries in order to create the block-wise structure. The algorithms I listed use only the matrix itself.

• I do have spatial information on the nodes. They are embedded on $R^3$
– 0x90
Feb 15 '19 at 15:38
• @0x90 but how is adjacency connected with it? Is it more likely for the graph nodes to be connected if they are close together in $\mathbb R^3$ as opposed to farther separated nodes? Feb 15 '19 at 16:04
• I have a solution with many particles and I build its pairwise distance matrix, then I apply some threshold to convert it to binary matrix. There will edge if two nodes are close in $\mathbf R^3$
– 0x90
Feb 15 '19 at 16:06
• @0x90 what is the application of this distance matrix? Isn't it preferable to use some partitioning algorithm (say octree) to begin with and renumber your nodes on that level without going to pairwise distances? Feb 15 '19 at 19:32
• this sounds like a good idea. So what would be a good way to go about it?
– 0x90
Feb 15 '19 at 20:16