  The Adjusted Rand Index ($ARI$) is arguably one of the most popular measures
for cluster comparison. The adjustment of the $ARI$ is based on a
hypergeometric distribution assumption which is unsatisfying from a modeling
perspective as (i) it is not appropriate when the two clusterings are
dependent, (ii) it forces the size of the clusters, and (iii) it ignores
randomness of the sampling. In this work, we present a new "modified" version
of the Rand Index. First, we redefine the $MRI$ by only counting the pairs
consistent by similarity and ignoring the pairs consistent by difference,
increasing the interpretability of the score. Second, we base the adjusted
version, $MARI$, on a multinomial distribution instead of a hypergeometric
distribution. The multinomial model is advantageous as it does not force the
size of the clusters, properly models randomness, and is easily extended to the
dependant case. We show that the $ARI$ is biased under the multinomial model
and that the difference between the $ARI$ and $MARI$ can be large for small $n$
but essentially vanish for large $n$, where $n$ is the number of individuals.
Finally, we provide an efficient algorithm to compute all these quantities
($(A)RI$ and $M(A)RI$) by relying on a sparse representation of the contingency
table in our \texttt{aricode} package. The space and time complexity is linear
in the number of samples and importantly does not depend on the number of
clusters as we do not explicitly compute the contingency table.
