dodiscover.metrics.toporder_divergence

dodiscover.metrics.toporder_divergence(true_graph, order)

Compute topological ordering divergence.

Topological order divergence is used to compute the number of false negatives, i.e. missing edges, associated to a topological order of the nodes of a graph with respect to the ground truth structure. If the topological ordering is compatible with the graph ground truth, the divergence is equal to 0. In the worst case of completely reversed ordering, toporder_divergence is equals to P, the number of edges (positives) in the ground truth graph. Note that the divergence defines a lower bound for the Structural Hamming Distance.

Parameters:

true_graphNetworkxGraph

Input groundtruth directed acyclic graph.

orderList[int]

A topological ordering on the nodes of the graph.

Returns:

errint

Sum of the number of edges of A not admitted by the given order.