# Evaluation and Benchmarking¶

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

implements two families of evaluation strategies:

*Internal*evaluation through fitness scores;*External*evaluation through partitions comparison.

Moreover, `cdlib`

integrates both standard *synthetic network benchmarks* and *real networks with annotated ground truths*, thus allowing for testing identified communities against ground-truths.

Finally, `cdlib`

also provides a way to *rank* clustering results generated by a set of algorithms over a given input graph.

Note

The following lists are aligned to CD evaluation methods available in the *GitHub main branch* of cdlib.

## Internal Evaluation: Fitness scores¶

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

implements the following quality scores:

`avg_distance` (graph, communities, **kwargs) |
Average distance. |

`avg_embeddedness` (graph, communities, **kwargs) |
Average embeddedness of nodes within the community. |

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

`avg_transitivity` (graph, communities, **kwargs) |
Average transitivity. |

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

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

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

`expansion` (graph, community, summary) |
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. |

`hub_dominance` (graph, communities, **kwargs) |
Hub dominance. |

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

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

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

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

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

`scaled_density` (graph, communities, **kwargs) |
Scaled density. |

`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, lmbd, …) |
The modularity density is one of several propositions that envisioned to palliate the resolution limit issue of modularity based measures. |

`modularity_overlap` (graph, communities, weight) |
Determines the Overlapping Modularity of a partition C on a graph G. |

`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) |

## External Evaluation: Partition Comparisons¶

It is often useful to compare different graph partition to assess their resemblance.
`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) |

## Synthetic Benchmarks¶

External evaluation scores can be fruitfully used to compare alternative clusterings of the same network, but also to asses to what extent an identified node clustering matches a known *ground truth* partition.

To facilitate such standard evaluation task, `cdlib`

exposes a set of standard synthetic network generators providing topological community ground truth annotations.

In particular, `cdlib`

make available benchmarks for:

*static*community discovery;*dynamic*community discovery;*feature-rich*(i.e., node-attributed) community discovery.

All details can be found in the dedicated page.

## Networks With Annotated Communities¶

Although evaluating a topological partition against an annotated “semantic” one is not among the safest path to follow [Peel17], `cdlib`

natively integrates well-known medium-size network datasets with ground-truth communities.

Due to the non-negligible sizes of such datasets, we designed a simple API to gather them from a dedicated remote repository transparently.

All details on remote datasets can be found on the dedicated page.

## Ranking Algorithms¶

Once a set of alternative clusterings have been extracted from a given network, is there a way to select the *best* one given a set of target fitness functions?

`cdlib`

exposes a few standard techniques to address such an issue: all details can be found in the dedicated documentation page.

[Peel17] | Peel, Leto, Daniel B. Larremore, and Aaron Clauset. “The ground truth about metadata and community detection in networks.” Science advances 3.5 (2017): e1602548. |