A question about stability of clustering I'm reading a paper about interactive clustering, and I'm stuck with a definition about stability property of a clustering (based on this paper): !enter image description here What I understand is that $A$ and $A$ are samples of the data, and a clustering algorithm $C$ is stable for all $A$ and $A$`. If, I'm correct, the similarity function $S(A, A')$ close to $0$ if they are similar. What I don't understand is why they use $\backslash$ (set difference) and I can't understand why $S(A, C_{i} \backslash A) > S(A, A')$

It means that the similarity between any subset $A$ of any cluster $C_i$ and the remaining nodes of $C_i$ should be greater than the similarity between $A$ and any subset $A'$ of any other cluster $C_j$.

Basically, the author mean that **intra** -cluster similarity should be greater than **inter** -cluster similarity for any subset of any clusters.

They use set difference, because they want to compare the intra-cluster similarity with inter-cluster similarity. To do this, they take any cluster $C_i$ and any subset of $C_i$, then check how it connects with the remaining of $C_i$ : $C_i\backslash A$. Then they check how $A$ connects with any part $A'$ of any other cluster $C_j$.