I want to construct a complete graph where each node is connected to every other

Question

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

Explanation / Answer

I suggest you start by reading about standard clustering algorithms and methods for clustering. You could start with Wikipedia: cluster analysis and hierarchical clustering, then move on to textbooks or online resources. Especially, check out hierarchical clustering to see if any of its methods might do what you want.

It sounds like you're not quite sure what you want. So, if you learn more about standard clustering methods, you might be in a better position to formulate a narrower, more focused question -- or if you're lucky, maybe you'll find a solution you're happy with.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.