Let's say I have a simple graph of undirected, weighted edges. I want to agglomerate nodes one-at-a-time by combining the two nodes which have the highest weighted edge, recalculating remaining edge weights by summing, and iterating. So if the starting graph looks like this:

enter image description here

A and B would be combined, and the weight of the edge from AB-C would be the sum of the original A-C and B-C edges (2+2):

enter image description here

A second iteration would combine AB and C and then we have:

enter image description here

Is there a name for this kind of procedure? I'd like to implement something like this in R. I suspect functions for this already exist somewhere.

Reading about agglomerative hierarchical clustering, K-means, etc., it seems like they're generally performed using dissimilarity measures calculated by comparing vectors of measures associated with the items to be agglomerated, but I don't think that's the same logic for what I have in mind, since I'm using graph data (an adjacency matrix) rather that attribute data. Having trouble finding the right keywords for this. Thank you!

  • $\begingroup$ You probably wanted averaging, and not the summing. After AB cluster is formed, its affinity to C is (2+2)/2=2, and not 2+2=4 which looks strange to me. The averaging strategy is called between-group average linkage method (stats.stackexchange.com/a/217742/3277). $\endgroup$ – ttnphns Jul 19 '18 at 6:33
  • $\begingroup$ In my situation, edge weight represents counts of movements between the nodes, so I believe summing rather than averaging is appropriate here. $\endgroup$ – lost Jul 19 '18 at 8:13
  • $\begingroup$ Summing gives fast advantage to clusters with more points (vertices) already. But it is fancy, you're the boss... Take the standard agglomerative hierarchical clustering algo using Lance-Williams formula - find (it's easy in the internet or books) how that formula looks for the between-group average linkage method (also known by acronym UPGMA), and modify the formula - replace averaging by summing (that is, use denominator 1 instead of the one used there). Thus, you get an open source code and modify the calculation of the formula there. $\endgroup$ – ttnphns Jul 19 '18 at 10:34

Your Answer

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

Browse other questions tagged or ask your own question.