deriving clusters from mst

I have been using the mst utility in R as a clustering tool.

g = graph_from_adjacency_matrix(adj, weighted = TRUE)
mst ← minimum.spanning.tree(g)
plot(mst)

To generate:

There are 34 nodes in this graph.

mst
mst
IGRAPH a203ffa DNW- 34 33 –

  • attr: name (v/c), weight (e/n)
  • edges from a203ffa (vertex names):
    [1] 1 ->504 1 ->522 38 ->1 78 ->758 226->522 293->522 293->526 498->499
    [9] 499->500 500->501 501->502 502->503 503->504 522->125 522->257 522->524
    [17] 522->525 523->522 754->758 755->758 756->758 757->755 758->13 758->759
    [25] 760->765 763->765 764->765 765->1 765->13 765->44 765->93 765->761
    [33] 765->762

There are 4 distinct groupings in plot(mst). Is there a way to recover these
groupings? Using str(mst) I do not see a way to do this. mst[[1:34]] does not
yield anything useful in this regard.

Any other procedures would be helpful.

Regards,
DGC

There may be, if you can provide a mathematically precise description of what you mean by “grouping”. The fact that they appear clustered in a plot does not mean much.

igraph has multiple community detection methods, which you can use either on your original graph or this tree. The function names all start with cluster_. That said, I would advise caution using minimum spanning trees this way.

1 Like