The Meaning of Dissimilar: An Evaluation of Various Similarity Quantification Approaches Used to Evaluate Community Detection Solutions

Evaluating a community detection method involves
measuring the extent to which the resulted solution, i.e clustering,
is similar to an optimal solution, a ground truth. Different
normalized similarity indices have been proposed in the literature
to quantify the extent to which two clusterings are similar where
1 refers to a perfect agreement between them (i.e the two clusterings are identical) and 0 refers to a perfect disagreement. While
interpreting the similarity score 1 seems to be intuitive, it does not
seem to be so when the similarity score is otherwise suggesting
a level of disagreement between the compared clusterings. That
is because there is no universal definition of dissimilarity when
it comes to comparing two clusterings. In this paper, we address
this issue by first providing a taxonomy of similarity indices
commonly used for evaluating community detection solutions.
We then elaborate on the meaning of clusterings dissimilarity
and the types of possible dissimilarities that can exist among two
clusterings in the context of community detection. We perform an
extensive evaluation to study the behaviour of different similarity
indices as a function of the dissimilarity type with both disjoint
and non-disjoint clusterings. We finally provide practitioners with
some insights on which similarity indices to use for the task at
hand and how to interpret their values