# Evaluation¶

The evaluation of Community Discovery algorithms is not an easy task.
`CDlib`

implements two families of evaluation strategies:

- Internal evaluation through quality scores
- External evaluation through partitions comparison

## Fitness Functions¶

Fitness functions allows to summarize the characteristics of a computed set of communities. `CDlib`

implements the following quality scores:

`average_internal_degree` (graph, community, …) |
The average internal degree of the community set. |

`conductance` (graph, community, **kwargs) |
Fraction of total edge volume that points outside the community. |

`cut_ratio` (graph, community, **kwargs) |
Fraction of existing edges (out of all possible edges) leaving the community. |

`edges_inside` (graph, community, **kwargs) |
Number of edges internal to the community. |

`expansion` (graph, community, **kwargs) |
Number of edges per community node that point outside the cluster. |

`fraction_over_median_degree` (graph, …) |
Fraction of community nodes of having internal degree higher than the median degree value. |

`internal_edge_density` (graph, community, **kwargs) |
The internal density of the community set. |

`normalized_cut` (graph, community, **kwargs) |
Normalized variant of the Cut-Ratio |

`max_odf` (graph, community, **kwargs) |
Maximum fraction of edges of a node of a community that point outside the community itself. |

`avg_odf` (graph, community, **kwargs) |
Average fraction of edges of a node of a community that point outside the community itself. |

`flake_odf` (graph, community, **kwargs) |
Fraction of nodes in S that have fewer edges pointing inside than to the outside of the community. |

`significance` (graph, communities, **kwargs) |
Significance estimates how likely a partition of dense communities appear in a random graph. |

`size` (graph, communities, **kwargs) |
Size is the number of nodes in the community |

`surprise` (graph, communities, **kwargs) |
Surprise is statistical approach proposes a quality metric assuming that edges between vertices emerge randomly according to a hyper-geometric distribution. |

`triangle_participation_ratio` (graph, …) |
Fraction of community nodes that belong to a triad. |

`purity` (communities) |
Purity is the product of the frequencies of the most frequent labels carried by the nodes within the communities |

Among the fitness function a well-defined family of measures is the Modularity-based one:

`erdos_renyi_modularity` (graph, communities, …) |
Erdos-Renyi modularity is a variation of the Newman-Girvan one. |

`link_modularity` (graph, communities, **kwargs) |
Quality function designed for directed graphs with overlapping communities. |

`modularity_density` (graph, communities, **kwargs) |
The modularity density is one of several propositions that envisioned to palliate the resolution limit issue of modularity based measures. |

`newman_girvan_modularity` (graph, communities, …) |
Difference the fraction of intra community edges of a partition with the expected number of such edges if distributed according to a null model. |

`z_modularity` (graph, communities, **kwargs) |
Z-modularity is another variant of the standard modularity proposed to avoid the resolution limit. |

Some measures will return an instance of `FitnessResult`

that takes together min/max/mean/std values of the computed index.

`FitnessResult` (min, max, score, std) |

## Partition Comparisons¶

It is often useful to compare different graph partition to assess their resemblance (i.e., to perform ground truth testing).
`CDlib`

implements the following partition comparisons scores:

`adjusted_mutual_information` (first_partition, …) |
Adjusted Mutual Information between two clusterings. |

`adjusted_rand_index` (first_partition, …) |
Rand index adjusted for chance. |

`f1` (first_partition, second_partition) |
Compute the average F1 score of the optimal algorithms matches among the partitions in input. |

`nf1` (first_partition, second_partition) |
Compute the Normalized F1 score of the optimal algorithms matches among the partitions in input. |

`normalized_mutual_information` (…) |
Normalized Mutual Information between two clusterings. |

`omega` (first_partition, second_partition) |
Index of resemblance for overlapping, complete coverage, network clusterings. |

`overlapping_normalized_mutual_information_LFK` (…) |
Overlapping Normalized Mutual Information between two clusterings. |

`overlapping_normalized_mutual_information_MGH` (…) |
Overlapping Normalized Mutual Information between two clusterings. |

`variation_of_information` (first_partition, …) |
Variation of Information among two nodes partitions. |

Some measures will return an instance of `MatchingResult`

that takes together mean and standard deviation values of the computed index.

`MatchingResult` (score, std) |