Matrix clustering in Mathematica?

Question

Suppose I have a square matrix $M$, which you can think of as the weighted adjacency matrix of a graph $G$. I want to order the vertices of $G$ in such a way that the entries of the matrix $M$ are clustered. By this I mean that the weights that are close in value should appear close in $M$.

I know Mathematica has some clustering algorithms implemented. How can I do this with Mathematica?

Answer 1

Spectral clustering might be a good candidate here. Generally, spectral clustering works as following:

1. Find a few largest eigenvectors of the adjacency matrix by magnitude, let's say we choose largest M vectors.

2. Treat each vertex as a N dimensional one-hot unit vector (where N is the number of vertices). Project each vertex into M dimensional "feature" space using the eigenvectors. This can be trivially done by transposing the MxN matrix of eigenvectors. In practice, M can be much smaller than N.

3. Use general purpose clustering algorithm in the "feature space", such as k-means.

(*sample input*)
nPoints = 2048;
nFeatureDim = 8;
nClusters = 18;
points = Normalize /@ RandomReal[{-1., 1.}, {nPoints, 3}];
adjMatrix = Power[DistanceMatrix[points], 4];
(*cluster on feature space*)
features = Transpose@Eigenvectors[adjMatrix, nFeatureDim];
clusters = FindClusters[features -> Range[nPoints], nClusters, Method ->"KMeans"];
sortedPoints = points[[#]] & /@ clusters;
(*make a render*)
colors = RGBColor /@ Tuples[{{0, 1}, {0, 0.5, 1}, {0, 0.5, 1}}];
vectorRender = Graphics3D[Transpose[{colors, Point /@ sortedPoints}]]

The above example uses a dense matrix. Finding eigenvectors should work equally well on sparse matrices.

Answer 2

"By this I mean that the weights that are close in value should appear close in M." Does this make sense if M represents a weight adjacency matrix? The clustered matrix would not be one anymore. You can just cluster the flattened list. Is the point of clustering a weighted adjacency matrix not rather that strongly connected vertices are clustered together? If yes, possible way: Transform into an actual graph object, cluster, and use the reordered list of vertex indices to resort the matrix.

MGraph=WeightedAdjacencyGraph[M];
MClusters=FindGraphCommunities[MGraph];(*Find strongly connected clusters*)
MResort=Flatten[MClusters];
MClustered=M[[;;,MResort]](*Reorder rows*)
MClustered=MClustered[[MResort,;;]](*Reorder columns*)

Perhaps there is also a way without transformation into a graph?