Documentation on existing tables of External Validation methods

[BradKML]

Is your feature request related to a problem? Please describe.

There are set-matching and other external indices for comparing expected community labels and output labels from a CD algorithm, it is something that is worth noting. separate from #114 as they seem irrelevant from one another.

• Adapting the right measures for K-means clustering
• Set Matching Measures for External Cluster Validity
• A Study on the Performance of Similarity Indices and its Relationship with Link Prediction: a Two-State Random Network Case

[github-actions]

Thanks for submitting your first issue!

[BradKML]

Also if we are doing pair counting:

• Generalized Pair-Counting Similarity Measures for Clustering and Cluster Ensembles
• Ground truth bias in external cluster validity indices
• Systematic Analysis of Cluster Similarity Indices: Towards Bias-free Cluster Validation

[BradKML]

https://github.com/ftheberge/graph-partition-and-measures

[BradKML]

And for internal validation: https://nas.ewi.tudelft.nl/people/Piet/papers/TUDreport20111111_MetricList.pdf

[BradKML]

I drafted some of the external indices for pair counting

ARI = a - (a+b)*(a+c)/total
Baulieu_1 = 1- (total*(b+c)+(b-c)**2)/(total**2)
Baulieu_2 = 1- (a*d+b*c)/(total**2)
Correlation_Coefficient = (a*d-b*c)/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Czekanowski = 2*a/(2*a+b+c)
Fager_McGowan = a/sqrt((a+b)*(c+d))-1/(2*sqrt(a+b)) # Asymmetric
Fowlkes_Mallows = a/sqrt((a+b)*(a+c))
Gamma = (total*a-(a+b)*(a+c))/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Goodman_Kruskal = (a*d-b*c)/(a*d+b*c)
Gower_Legendre = (a+d)/(a+(b+c)/2+d)
Hamann = ((a+d)-(b+c))/total
Hubert = (a+d)-(b+c)/total
Jaccard = a/(a+b+c)
Kulczynski = (a/(a+b)+a/(a+c))/2
McConnaughey = (a**2-b*c)/((a-b)*(a+c)) # Asymmetric
Minkowski = sqrt((b+c)/(a+b)) # Asymmetric
Mirkin = 2*(b+c)/total
Pearson = (a*d-b*c)/((a+b)*(a+c)*(c+d)*(b+d))
Pierce = (a*d-b*c)/((a+c)*(b+d))
Rand = (a+d)/total
Russel_Rao = a/total
Rogers_Tanimoto = (a+d)/(a+2(b+c)+d)
Sokal_Sneath_1 = (a/(a+b)+a/(a+c)+d/(b+d)+d/(c+d))/4
Sokal_Sneath_2 = a/(a+2*(b+c))
Sokal_Sneath_3 = (a*d)/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Wallance = a/(a+b) # Asymmetric
Yule = ((a*d)-(b*c))/((a*b)-(c+d)) # Asymmetric

[BradKML]

For:

• https://arxiv.org/pdf/1512.01286.pdf Adjusted Mutual Information and Adjusted Purity
• https://hal.archives-ouvertes.fr/hal-00802923/document Modified Purity, Modified ARI, Modified NMI (adding a topological variable)

[GiulioRossetti]

I drafted some of the external indices for pair counting

ARI = a - (a+b)*(a+c)/total
Baulieu_1 = 1- (total*(b+c)+(b-c)**2)/(total**2)
Baulieu_2 = 1- (a*d+b*c)/(total**2)
Correlation_Coefficient = (a*d-b*c)/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Czekanowski = 2*a/(2*a+b+c)
Fager_McGowan = a/sqrt((a+b)*(c+d))-1/(2*sqrt(a+b)) # Asymmetric
Fowlkes_Mallows = a/sqrt((a+b)*(a+c))
Gamma = (total*a-(a+b)*(a+c))/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Goodman_Kruskal = (a*d-b*c)/(a*d+b*c)
Gower_Legendre = (a+d)/(a+(b+c)/2+d)
Hamann = ((a+d)-(b+c))/total
Hubert = (a+d)-(b+c)/total
Jaccard = a/(a+b+c)
Kulczynski = (a/(a+b)+a/(a+c))/2
McConnaughey = (a**2-b*c)/((a-b)*(a+c)) # Asymmetric
Minkowski = sqrt((b+c)/(a+b)) # Asymmetric
Mirkin = 2*(b+c)/total
Pearson = (a*d-b*c)/((a+b)*(a+c)*(c+d)*(b+d))
Pierce = (a*d-b*c)/((a+c)*(b+d))
Rand = (a+d)/total
Russel_Rao = a/total
Rogers_Tanimoto = (a+d)/(a+2(b+c)+d)
Sokal_Sneath_1 = (a/(a+b)+a/(a+c)+d/(b+d)+d/(c+d))/4
Sokal_Sneath_2 = a/(a+2*(b+c))
Sokal_Sneath_3 = (a*d)/sqrt((a+b)*(a+c)*(c+d)*(b+d))
Wallance = a/(a+b) # Asymmetric
Yule = ((a*d)-(b*c))/((a*b)-(c+d)) # Asymmetric

That's interesting.
Could you please specify what each letter represents? otherwise, some definitions are not straightforward to implement.

[BradKML]

@GiulioRossetti so A is True Positive pairs (when nodes A and B are in the same partition in both cases), and D is True Negative pairs. (when nodes A and B are in a different partition in both cases), and B/C is when the node pair of the ground truth does not match the node pair of the prediction.

For further reference:

• http://www.comparingpartitions.info/index.php?link=Tut14
• http://www.comparingpartitions.info/?link=Tut8 (Using Wallace as example for Asymmetric)

[GiulioRossetti]

@GiulioRossetti so A is True Positive pairs (when nodes A and B are in the same partition in both cases), and D is True Negative pairs. (when nodes A and B are in a different partition in both cases), and B/C is when the node pair of the ground truth does not match the node pair of the prediction.

Thanks for the clarification. Ok per A (which is TP) and D (which is TN) but B and C are not interchangeable. I assume that B is FP and C is FN, am I right?

[BradKML]

@GiulioRossetti they are interchangeable in most cases, but in the Fager_McGowan, McConnaughey, Minkowski, Wallance and Yule they are not.

In Wallace(A,B)=a/(a+b) case, b is when the node pair is in the same partition in A but different partitions in B.
A would-be ground truth and B would be predicted partition

[BradKML]

A weird side thought:

1. The pair-counting methodology can be converted into a distance metric (see https://en.wikipedia.org/wiki/Jaccard_index#Other_definitions_of_Tanimoto_distance )
2. Alternate implementation discovery in https://github.com/n-serrette/Cluster_Index and https://github.com/MartijnGosgens/validation_indices/blob/master/PairCountingIndices.py