Concepts#

This page provides a conceptual overview of backbone extraction and how the methods in nx-backbone are organized.

What is backbone extraction?#

Real-world networks are often dense and noisy. Backbone extraction identifies the most important substructure of a network by removing edges that are redundant, statistically insignificant, or structurally unimportant. The result is a sparser graph that preserves the essential structure of the original.

Taxonomy of methods#

The 87 functions in nx-backbone are organized into ten modules based on the approach they take. The method taxonomy aligns with the categories used in netbone (Yassin et al., 2023; https://gitlab.liris.cnrs.fr/coregraphie/netbone), extended with a hypergraph module for higher-order networks.

Statistical methods#

The statistical module provides eight methods that test whether each edge’s weight is statistically significant under a null model. These methods produce a p-value or score for each edge, or a keep flag.

  • disparity_filter() – uniform null model (Serrano et al., 2009)

  • noise_corrected_filter() – Bayesian noise-corrected lift score with a standard deviation (Coscia & Neffke, 2017)

  • marginal_likelihood_filter() – binomial null considering both endpoints (Dianati, 2016)

  • ecm_filter() – maximum-entropy null model (Gemmetto et al., 2017)

  • lans_filter() – nonparametric empirical CDF (Foti et al., 2011)

  • polya_filter() – Pólya urn null with a reinforcement parameter that tolerates heterogeneous weights (Marcaccioli & Livan, 2019)

  • gloss_filter() – global null that keeps the topology and draws weights from the observed weight distribution (Radicchi et al., 2011)

  • multiple_linkage_analysis() – dominant links per node by fitting ideal distributions (Van Nuffel, 2007); method="lans" thresholds LANS p-values instead, as version 0.2 did

The noise-corrected backbone keeps an edge when its score exceeds delta standard deviations (nc_score > delta * nc_sdev, with delta = 1.64 in the paper). That rule is not a calibrated test, so nc_pvalue is by default the exact binomial p-value of the same null model; pvalue_method="delta" expresses the paper’s rule as a p-value. Multiple linkage analysis is not a significance test: for each node it chooses how many links are dominant by comparing the node’s sorted weight shares with ideal “one dominant link”, “two equal links”, … distributions (by the coefficient of determination, as restated by Van Nuffel et al., 2010), whereas LANS gives every link a p-value from its node’s empirical weight distribution.

P-values can be corrected for multiple comparisons with adjust_pvalues() or the mtc argument of threshold_filter() (Bonferroni, Holm, Hochberg, Benjamini-Hochberg, Benjamini-Yekutieli). The disparity_filter, noise_corrected_filter, marginal_likelihood_filter, ecm_filter, and lans_filter methods also accept signed=True for a two-tailed test that keeps significantly strong (+1) and significantly weak (-1) edges, each tagged with a "sign" attribute. The sign is +1 when the upper-tail p-value is smaller than the lower-tail one and -1 otherwise, so an edge whose two tails are exactly equal is signed -1, as in R backbone 3.0.4; the same rule applies to the signed bipartite null models. With missing_as_zero=True they also test every pair of nodes that has no edge, as an edge of weight 0, so a signed backbone can contain pairs that interact significantly less than expected (Backbone 3.0’s missing_as_zero). The result then has one edge per tested node pair, which takes \(O(n^2)\) memory.

Each null model assumes something about the weights. The disparity filter assumes that a node’s weight shares are uniform spacings, which holds for independent exponential weights; disparity_filter(a=...) relaxes this to a one-parameter family whose a can be fitted (a="ml"). The marginal likelihood, ECM, and noise-corrected filters treat weights as counts of events, so their results depend on the unit, which unit= sets. transform_weights() applies a log, power, or other transform before scoring. Weights, Units, and Transforms lists which methods a rescaling or an increasing transform leaves unchanged.

Structural methods#

The structural module provides fourteen methods that use topological properties of the network directly, without hypothesis testing.

Proximity methods#

The proximity module provides twelve methods that score each edge based on how similar the neighborhoods of its endpoints are. High-scoring edges are structurally embedded within communities, while low-scoring edges tend to be bridges.

Methods include jaccard_backbone(), dice_backbone(), cosine_backbone(), adamic_adar_index(), resource_allocation_index(), and more.

Hybrid methods#

The hybrid module contains glab_filter(), which combines global betweenness information with local degree information (Zhang et al., 2014).

Bipartite methods#

The bipartite module provides methods for extracting significant edges from bipartite graph projections:

Hypergraph methods#

The hypergraph module backbones higher-order networks (hypergraphs) directly, rather than dyadic graphs. Unlike the projection-based bipartite methods, which reduce a hypergraph to a weighted pairwise graph, these methods return a sub-hypergraph (a subset of hyperedges).

Because a hypergraph backbone is a subset of hyperedges rather than a graph, this module returns a HypergraphBackbone (or ValidatedHypergraph) result instead of using the filters utilities.

The hypergraph_io helpers convert hyperedge lists to and from a NetworkX incidence bipartite graph (so the bipartite projection backbones apply to hypergraphs), the HIF interchange format, and the xgi / HyperNetX / HypergraphX / HAT hypergraph classes (optional, imported lazily).

Unweighted methods#

The unweighted module provides sparsification methods for unweighted graphs using a four-step pipeline of scoring, normalization, filtering, and optional connectivity restoration:

Temporal networks#

The temporal module takes a network observed over time in any of three forms: snapshots (a dict or list of graphs), events (a multigraph with one timed edge per event), or spans (a multigraph whose edges last from start to end, read as the half-open interval [start, end)). temporal_form() tells them apart and convert_temporal() converts between them. Events and spans become snapshots by binning time into steps of width freq. Converting snapshots to events or spans and back is lossless. See Temporal networks: formats and conversions for worked examples.

Temporal backbones: presence and eligible steps#

The temporal backbone scores (observation_fraction(), persistence(), backbone_stability(), weight_trend(), edge_persistence_hmm() and kalman_backbone()) work on steps: the snapshots, or the bins of width freq that events and spans fall into. A node is present in a step if it is in that snapshot (isolated or not); after binning, only if it has an event or span in that step. An edge that is missing from a step means one of two things:

  • both endpoints are present, so the edge could have been seen and was not: an observed zero (weight 0);

  • an endpoint is absent, so nothing is known about the edge in that step.

An edge’s eligible steps are the steps in which both of its endpoints are present. The scores count only those, so a node that joins late is not penalized for the steps before it existed. In this example "c" joins at step 2:

>>> import networkx as nx
>>> import nx_backbone as nb
>>> S = [
...     nx.Graph([("a", "b")]),
...     nx.Graph([("a", "b")]),
...     nx.Graph([("b", "c")]),
...     nx.Graph([("a", "b"), ("b", "c")]),
... ]
>>> S[2].add_node("a")  # present at step 2, without edges
>>> H = nb.observation_fraction(S)
>>> H["a"]["b"]["obs_fraction"], H["a"]["b"]["n_eligible"]
(0.75, 4)
>>> H["b"]["c"]["obs_fraction"], H["b"]["c"]["n_eligible"]
(1.0, 2)

("a", "b") is missing at step 2 while both endpoints are present, an observed zero, so it is seen in 3 of 4 eligible steps. ("b", "c") is eligible only from step 2, when "c" joins, and is seen in both of those steps. Counting all four steps would give it 0.5 and treat the steps before "c" existed as evidence against the edge. A node that leaves early is handled the same way: its edges are unknown, not zero, after it leaves.

Each score returns one static graph, the union of the observed edges with score attributes (and H.graph["temporal"], which records the steps and parameters), so the score-then-filter pattern below applies unchanged. See the Temporal Backbones tutorial.

The score-then-filter pattern#

Most backbone methods follow a two-step pattern:

  1. Score: Apply a backbone method to annotate each edge with a score (p-value, similarity, salience, etc.). The method returns a copy of the graph with the score as an edge attribute.

  2. Filter: Use a function from the filters module to extract the backbone by selecting edges based on their score.

For example:

# Step 1: Score edges
H = nb.disparity_filter(G)  # adds "disparity_pvalue" attribute

# Step 2: Filter edges
backbone = nb.threshold_filter(H, "disparity_pvalue", 0.05)

Many structural and unweighted methods expose boolean edge flags (for example metric_keep or sparsify_keep). These still follow score-then-filter:

scored = nb.metric_backbone(G)               # adds "metric_keep"
backbone = nb.boolean_filter(scored, "metric_keep")

Evaluation#

The measures module provides metrics for evaluating how well a backbone preserves the properties of the original graph: