# Algorithm for Graph merge and recompute

I want to construct a complete graph where each node is connected to every other node. The link between the nodes give a distance function (does not follow triangle inequality) between them. What I require is to merge the closest nodes, (bounded by a threshold) into a single node and recompute the graph each time, recursively. This is because if two nodes are merged, then all the links connected to the new node has to be updated with the newly computed distance for the new edge. Since its a complete graph this would be an expensive operation.

I would have a large number of nodes with $N*(N-1)/2$ links for $N$ nodes , and $N=60$ or more , What I want to do is to reduce this complete graph into clusters of sub graphs with low intra node distance, yet with a relatively high distance between the subgraphs. So,How can I go about solving this problem?

This is like applying the graph partitioning techniques to complete graphs.

One of the solutions is this paper which proposes the normalized cut criterion for partitioning the graph minimizing normalized cuts on graphs which is clearly NP-complete,Is there a practically efficient way and what are the recent developments to achieve this?

So what I want is an efficient solution to the above problem which is not NP complete ? Since this problem is NP Complete , answers using randomization or approximation methods would be welcome

• Can you define precisely what characteristics you want a solution to have? Or, is that part of the question? I don't see a specification of "low intra node distance" (what counts as low? what is the definition of intra node distance?) nor a definition of distance between subgraphs. So, are you looking for help formalizing this more precisely? If so, you'll probably need to tell us more about the application and how you will use the result of the clustering. On the other hand, if you have a specific definition/set of metrics in mind, then I recommend you edit the question to provide it.
– D.W.
Aug 29, 2013 at 8:44
• You could run Kruskal's algorithm and stop it when the next edge becomes too long. Aug 29, 2013 at 8:47
• How distance is defined does not matter as different applications would have different functions to compute them, Moreover all distances are relative ,so a low distance means low in context of the graph relative to other edges,what matters is the algorith to efficiently generate normalized mincuts as explained in the refered paper @D.W. Aug 29, 2013 at 8:47

• @CS101, Hierarchical clustering can give you a graph as output. Pick some level to stop the clustering. Now merge all nodes that are in the same cluster into a single node. This gives you a graph, based upon the merger process. (In other words: each cluster becomes a single merged node, and there's an edge from cluster $u$ to cluster $v$ iff there's a node $u'$ from the original graph in cluster $u$ and a node $v'$ from the original graph in cluster $v$ such that there was an edge $u'\to v'$ in the original graph.)