Les Miserables Benchmark#

This benchmark uses NetworkX’s built-in nx.les_miserables_graph() and applies a strict score-then-filter workflow for every method:

Run a scoring method that returns the full graph with edge attributes.
Apply a filter (threshold_filter, fraction_filter, or boolean_filter).
Report edge counts only from the filtered graph.

If the filtered graph has the same edge count as the original graph, issue a warning and re-test the method parameters.

Setup#

import warnings
import networkx as nx
import nx_backbone as nb

G = nx.les_miserables_graph()
G_unweighted = nx.Graph()
G_unweighted.add_nodes_from(G.nodes(data=True))
G_unweighted.add_edges_from(G.edges())

ORIGINAL_EDGES = G.number_of_edges()  # 254

def warn_if_no_reduction(name, filtered):
    if filtered.number_of_edges() == ORIGINAL_EDGES:
        warnings.warn(
            f"{name}: filtered graph has the same number of edges as "
            f"the original ({ORIGINAL_EDGES}). Re-test and validate.",
            UserWarning,
        )

Filtered Edge Counts#

All counts below are after explicit filtering. They are computed when the documentation is built, from the same method definitions whose counts the test suite pins (tests/test_les_miserables.py), so the table always matches the installed version of the library. Methods marked unweighted run on G_unweighted; every other method runs on the weighted graph G.

Method	Filter applied	Edges kept (of 254)
`disparity_filter()`	`disparity_pvalue < 0.05`	9
`noise_corrected_filter()`	`nc_pvalue < 0.05`	126
`noise_corrected_filter()` (`pvalue_method='delta'`)	`nc_pvalue < 0.05`	195
`noise_corrected_filter()` (`method='zscore'`)	`nc_score >= 2.0`	98
`marginal_likelihood_filter()`	`ml_pvalue < 0.05`	126
`ecm_filter()`	`ecm_pvalue < 0.05`	72
`lans_filter()`	`lans_pvalue < 0.05`	109
`multiple_linkage_analysis()`	`mla_keep` (boolean)	205
`multiple_linkage_analysis()` (`method='lans', alpha=0.05`)	`mla_keep` (boolean)	109
`polya_filter()`	`polya_pvalue < 0.05`	12
`gloss_filter()`	`gloss_pvalue < 0.05`	3
`global_threshold_filter()` (`threshold=2`)	`global_threshold_keep` (boolean)	157
`strongest_n_ties()` (`n=2`)	`strongest_n_ties_keep` (boolean)	146
`global_sparsification()` (`s=0.5`)	`global_sparsification_keep` (boolean)	127
`primary_linkage_analysis()`	`primary_linkage_keep` (boolean)	69
`edge_betweenness_filter()` (`s=0.5`)	`edge_betweenness_keep` (boolean)	127
`node_degree_filter()` (`min_degree=2`)	`node_degree_keep` (boolean)	237
`high_salience_skeleton()`	`salience >= 0.5`	76
`metric_backbone()`	`metric_keep` (boolean)	163
`ultrametric_backbone()`	`ultrametric_keep` (boolean)	118
`doubly_stochastic_filter()`	`ds_weight >= 0.1`	109
`doubly_stochastic_filter()`	`ds_keep` (boolean)	187
`h_backbone()`	`h_backbone_keep` (boolean)	18
`modularity_backbone()` (`seed=42`)	`modularity_keep` (boolean)	72
`planar_maximally_filtered_graph()`	`pmfg_keep` (boolean)	162
`maximum_spanning_tree_backbone()`	`mst_keep` (boolean)	76
`neighborhood_overlap()`	top 30% by `overlap`	76
`jaccard_backbone()`	top 30% by `jaccard`	76
`dice_backbone()`	top 30% by `dice`	76
`cosine_backbone()`	top 30% by `cosine`	76
`hub_promoted_index()`	top 30% by `hpi`	76
`hub_depressed_index()`	top 30% by `hdi`	76
`lhn_local_index()`	top 30% by `lhn_local`	76
`preferential_attachment_score()`	top 30% by `pa`	76
`adamic_adar_index()`	top 30% by `adamic_adar`	76
`resource_allocation_index()`	top 30% by `resource_allocation`	76
`graph_distance_proximity()`	top 30% by `dist`	76
`local_path_index()`	top 30% by `lp`	76
`glab_filter()`	`glab_pvalue < 0.05`	56
`sparsify()`, unweighted	`sparsify_keep` (boolean)	174
`lspar()`, unweighted	`sparsify_keep` (boolean)	174
`local_degree()`, unweighted	`sparsify_keep` (boolean)	91

Reproducibility Script#

The table is generated from the case list below, kept in benchmarks/benchmarks/les_miserables.py in the source repository. Each case names a scorer, its keyword arguments, and the filter applied to its scores:

def _pvalue(method, attr):
    return Case(method, "threshold", attr, ALPHA, "below")


def _top(method, attr):
    return Case(method, "fraction", attr, TOP_FRACTION)


def _keep(method, attr, label=None, **kwargs):
    return Case(method, "boolean", attr, kwargs=kwargs, label=label)


WEIGHTED_CASES = [
    # Statistical
    _pvalue("disparity_filter", "disparity_pvalue"),
    _pvalue("noise_corrected_filter", "nc_pvalue"),
    Case(
        "noise_corrected_filter",
        "threshold",
        "nc_pvalue",
        ALPHA,
        "below",
        kwargs={"pvalue_method": "delta"},
        label="noise_corrected_filter(pvalue_method='delta')",
    ),
    Case(
        "noise_corrected_filter",
        "threshold",
        "nc_score",
        2.0,
        "above",
        kwargs={"method": "zscore"},
        label="noise_corrected_filter(method='zscore')",
    ),
    _pvalue("marginal_likelihood_filter", "ml_pvalue"),
    _pvalue("ecm_filter", "ecm_pvalue"),
    _pvalue("lans_filter", "lans_pvalue"),
    _keep("multiple_linkage_analysis", "mla_keep"),
    Case(
        "multiple_linkage_analysis",
        "boolean",
        "mla_keep",
        kwargs={"method": "lans", "alpha": ALPHA},
        label="multiple_linkage_analysis(method='lans', alpha=0.05)",
    ),
    _pvalue("polya_filter", "polya_pvalue"),
    _pvalue("gloss_filter", "gloss_pvalue"),
    # Structural
    _keep(
        "global_threshold_filter",
        "global_threshold_keep",
        "global_threshold_filter(threshold=2)",
        threshold=2,
    ),
    _keep("strongest_n_ties", "strongest_n_ties_keep", "strongest_n_ties(n=2)", n=2),
    _keep(
        "global_sparsification",
        "global_sparsification_keep",
        "global_sparsification(s=0.5)",
        s=0.5,
    ),
    _keep("primary_linkage_analysis", "primary_linkage_keep"),
    _keep(
        "edge_betweenness_filter",
        "edge_betweenness_keep",
        "edge_betweenness_filter(s=0.5)",
        s=0.5,
    ),
    _keep(
        "node_degree_filter",
        "node_degree_keep",
        "node_degree_filter(min_degree=2)",
        min_degree=2,
    ),
    Case("high_salience_skeleton", "threshold", "salience", 0.5, "above"),
    _keep("metric_backbone", "metric_keep"),
    _keep("ultrametric_backbone", "ultrametric_keep"),
    Case("doubly_stochastic_filter", "threshold", "ds_weight", 0.1, "above"),
    _keep("doubly_stochastic_filter", "ds_keep", "doubly_stochastic_filter (ds_keep)"),
    _keep("h_backbone", "h_backbone_keep"),
    _keep("modularity_backbone", "modularity_keep", seed=42),
    _keep("planar_maximally_filtered_graph", "pmfg_keep"),
    _keep("maximum_spanning_tree_backbone", "mst_keep"),
    # Proximity
    _top("neighborhood_overlap", "overlap"),
    _top("jaccard_backbone", "jaccard"),
    _top("dice_backbone", "dice"),
    _top("cosine_backbone", "cosine"),
    _top("hub_promoted_index", "hpi"),
    _top("hub_depressed_index", "hdi"),
    _top("lhn_local_index", "lhn_local"),
    _top("preferential_attachment_score", "pa"),
    _top("adamic_adar_index", "adamic_adar"),
    _top("resource_allocation_index", "resource_allocation"),
    _top("graph_distance_proximity", "dist"),
    _top("local_path_index", "lp"),
    # Hybrid
    _pvalue("glab_filter", "glab_pvalue"),
]

UNWEIGHTED_CASES = [
    Case("sparsify", "boolean", "sparsify_keep", weighted=False),
    Case("lspar", "boolean", "sparsify_keep", weighted=False),
    Case("local_degree", "boolean", "sparsify_keep", weighted=False),
]

Each case expands to one score-then-filter call, for example:

H = nb.threshold_filter(nb.disparity_filter(G), "disparity_pvalue", 0.05, mode="below")
H = nb.threshold_filter(nb.noise_corrected_filter(G), "nc_pvalue", 0.05, mode="below")
H = nb.boolean_filter(nb.multiple_linkage_analysis(G), "mla_keep")

From a checkout of the repository, the whole table can be reproduced with:

import warnings

from benchmarks.benchmarks.les_miserables import CASES, graph_for

for case in CASES:
    G = graph_for(case)
    filtered = case.run(G)
    if filtered.number_of_edges() == G.number_of_edges():
        warnings.warn(f"{case.name}: no edge was removed", UserWarning)
    print(case.name, filtered.number_of_edges())