0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Aug 29, 2013 at 8:44
  • 1
    $\begingroup$ You could run Kruskal's algorithm and stop it when the next edge becomes too long. $\endgroup$
    – adrianN
    Aug 29, 2013 at 8:47
  • $\begingroup$ 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. $\endgroup$
    – CS101
    Aug 29, 2013 at 8:47

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Heirarchical clustering is a good approximation bit it it does not serve my ultimate purpose as output is heirachical in tree form , I want the output to be a graph $\endgroup$
    – CS101
    Aug 29, 2013 at 8:54
  • $\begingroup$ @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.) $\endgroup$
    – D.W. ♦
    Aug 29, 2013 at 21:12
  • $\begingroup$ The problem is that the distance for each link needs to be recomputed each time a merger happens . Does heirarchical clustering accommodate this? $\endgroup$
    – CS101
    Sep 1, 2013 at 18:17
  • $\begingroup$ @CS101, yes, bottom-up (agglomerative) clustering can accomodate this. Again, I recommend that you read some background on clustering methods -- you should be able to answer this sort of question for yourself, once you read up on clustering and understand how standard methods work. $\endgroup$
    – D.W. ♦
    Sep 2, 2013 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.