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')$


1 Answer 1


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

  • $\begingroup$ Thanks, now it makes sense :) $\endgroup$
    – azer89
    Commented Mar 12, 2015 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .