0
$\begingroup$

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)

enter image description here

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:

enter image description here

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ I do have spatial information on the nodes. They are embedded on $R^3$ $\endgroup$
    – 0x90
    Commented Feb 15, 2019 at 15:38
  • $\begingroup$ @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? $\endgroup$
    – Anton Menshov ♦
    Commented Feb 15, 2019 at 16:04
  • $\begingroup$ 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$ $\endgroup$
    – 0x90
    Commented Feb 15, 2019 at 16:06
  • $\begingroup$ @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? $\endgroup$
    – Anton Menshov ♦
    Commented Feb 15, 2019 at 19:32
  • $\begingroup$ this sounds like a good idea. So what would be a good way to go about it? $\endgroup$
    – 0x90
    Commented Feb 15, 2019 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.