I am looking for a metric to compare several clustering solutions to a reference clustering that is known to be "correct". Specifically I have a set of millions of genes, and I wish to compare different clustering solutions of them to a known clustering of these genes, in order to find the best performing parameters and then apply these parameters to cluster a different set of genes.
If it were a smaller set, one option I thought of is to test for every pair in the clustering solution whether it is in the same cluster or a different one, and compare this to the reference clustering. This approach does not seem practical for the size of clustering I'm dealing with, plus - I assume there are well-established methods to deal with such problems (which I was unable to find).
What would be a good method/metric to compare a clustering solution to a given reference clustering?