# 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.