In my data, I have a defined a symmetrical relation $R$ where $R(i,j)=R(j,i)$ indicates that $i$ and $j$ are closed each other.

I need to find cliques $C_1,C_2,\dots,C_n$ where

  • $C_k\cap C_l=\emptyset$
  • and $\cup_k C_k = \{1,2,\dots\}$
  • and $\forall k\forall i,j\in C_{k}:R(i,j)$

The approach I use is agglomerative clustering with complete link: distance of $i,j$ for $R(i,j)$ is $0$ and for $\neg R(i,j)$ is $\infty$.

Is there another option to do that computationally more efficiently. I have several thousands of objects.

  • $\begingroup$ I think you've got a typo, not sure what "i and j are closed each other" means $\endgroup$ – jon_simon Jun 15 '18 at 23:13

The problem is NP-complete. There is no computationally efficient way that guarantees finding the maximum solution.

Complete link with AGNES is O(n³), but will not find optimum solutions. It is also not meant for binary properties. An edge based approach of the same algorithm would be much faster (but still same complexity class because of the worst case and same low quality).

If you want to find good cliques, read some literature on the maximum cliques problem.



Your Answer

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

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