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):
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$.