4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See FindClusters and/or ClusteringComponents $\endgroup$ – kglr Oct 13 '14 at 20:05
  • 1
    $\begingroup$ @kguler I have seen those functions, but I don't know how to use them to solve my problem. $\endgroup$ – becko Oct 13 '14 at 20:48
  • 1
    $\begingroup$ Good question.. $\endgroup$ – Daniel Lichtblau Oct 14 '14 at 1:00
  • $\begingroup$ One possible solution: 157557 $\endgroup$ – C. E. May 24 at 8:15
2
$\begingroup$

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.

spectral clustering on

| improve this answer | |
$\endgroup$
0
$\begingroup$

"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?

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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