agglomerative clustering of undirected weighted graph

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: 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): A second iteration would combine AB and C and then we have: 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!

• 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). – ttnphns Jul 19 '18 at 6:33
• In my situation, edge weight represents counts of movements between the nodes, so I believe summing rather than averaging is appropriate here. – lost Jul 19 '18 at 8:13
• 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. – ttnphns Jul 19 '18 at 10:34