Clustering: Clique vs. Agglomerative with Complete-Link

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.

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