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