  In the context of cluster analysis and graph partitioning, many external
evaluation measures have been proposed in the literature to compare two
partitions of the same set. This makes the task of selecting the most
appropriate measure for a given situation a challenge for the end user.
However, this issue is overlooked in the literature. Researchers tend to follow
tradition and use the standard measures of their field, although they often
became standard only because previous researchers started consistently using
them. In this work, we propose a new empirical evaluation framework to solve
this issue, and help the end user selecting an appropriate measure for their
application. For a collection of candidate measures, it first consists in
describing their behavior by computing them for a generated dataset of
partitions, obtained by applying a set of predefined parametric partition
transformations. Second, our framework performs a regression analysis to
characterize the measures in terms of how they are affected by these parameters
and transformations. This allows both describing and comparing the measures.
Our approach is not tied to any specific measure or application, so it can be
applied to any situation. We illustrate its relevance by applying it to a
selection of standard measures, and show how it can be put in practice through
two concrete use cases.
