I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies. Dependencies can be thought of as number of edges connected. I want to group those with maximum dependencies.

For example in the set $\{1,2,3\}$ and $\{3,5,7\}$ if $\{3,5,7\}$ have more dependencies i need to group $\{3,5,7\}$. I know the dependencies beforehand.

Which algorithm will help to solve this problem?

  • 1
    $\begingroup$ Your question seems under-specified. Can you give a more formal definition of dependencies and your task? Are you looking for the cluster deletion or cluster editing problem, also known as correlation clustering? This is an NP-hard problem, but admits an FPT-algorithm, so all hope is not lost. If you also want a bounded number of clusters, you can do it in almost subexponential time $2^{O(\sqrt{kp})}n^{O(1)}$ where $k$ is number of dependencies (edges) you can change and $p$ is the maximum number of clusters you allow. $\endgroup$
    – Pål GD
    Jun 19 '13 at 13:44
  • 1
    $\begingroup$ It sounds like you want to choose some set of subsets of vertices of a graph, such that the number of edges within each subset is as large as possible. But to make this meaningful, you need to either weight the clusters, so that vertices that are not connected in a subset reduce the measure you want to optimize, or you need to capture that subsets should not have too many edges between each other. Otherwise, the obvious thing is to just take all vertices as one big cluster. What is your missing condition? $\endgroup$ Jun 19 '13 at 15:09
  • $\begingroup$ @AndrásSalamon Whether graph partitioning algorithm fits my problem $\endgroup$
    – user5507
    Jun 22 '13 at 2:55
  • $\begingroup$ I repeat Pål's comment: you have left out some important part of your problem. To solve your problem as you state it, just take all nodes as one big cluster. You probably didn't mean that. What did you mean? $\endgroup$ Jun 22 '13 at 7:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.