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.