nx-backbone

Backbone extraction algorithms for complex networks, built on NetworkX.

This library provides about 110 functions across 14 modules for extracting backbone structures from weighted, unweighted, bipartite, temporal, and higher-order (hypergraph) networks. The public API is type-annotated (py.typed), and the graph-in, graph-out functions dispatch to NetworkX backends such as nx-parallel.

Full documentation: https://www.brianckeegan.com/nx-backbone/

Installation

pip install nx-backbone

For full functionality (required for statistical tests, bipartite methods, and some structural methods):

pip install nx-backbone[full]

Or install from source:

git clone https://github.com/brianckeegan/nx-backbone.git
cd nx-backbone
pip install -e ".[full]"

Modules

NetBone Core Coverage

Core method families used in netbone (Yassin et al., 2023) are represented here, including:

• Statistical: disparity_filter, marginal_likelihood_filter, ecm_filter, noise_corrected_filter, lans_filter, multiple_linkage_analysis, polya_filter, gloss_filter
• Structural: global_threshold_filter, global_sparsification, primary_linkage_analysis, edge_betweenness_filter, high_salience_skeleton, doubly_stochastic_filter, maximum_spanning_tree_backbone
• Hybrid: glab_filter

docs/design/yassin-2025-coverage.md checks the package method by method against the two comparative studies by Yassin et al. (2025). It covers all 15 methods, including the Pólya urn and GloSS filters.

Every backbone model in Neal's Backbone 3.0 R package is also covered (disparity, mlf, lans, sdsm, fdsm, fixedfill/fixedrow/fixedcol, bicm, fastball, and the backbone_from_* wrappers), including its hypergraph-projection input via hypergraph_to_bipartite, plus its cross-cutting features: multiple-testing correction (adjust_pvalues, threshold_filter(mtc=...)), signed backbones (signed=True adds a sign edge attribute), and SDSM-EC edge constraints (sdsm(prohibited=, required=)). See docs/design/backbone-3.0-coverage.md for the full coverage analysis.

Quick Start

import networkx as nx
import nx_backbone as nb

# Create a weighted graph
G = nx.les_miserables_graph()

# 1) Score edges
scored = nb.disparity_filter(G)

# 2) Filter edges
backbone = nb.threshold_filter(scored, "disparity_pvalue", 0.05)

# Compare backbone to original
print(f"Edges kept: {nb.edge_fraction(G, backbone):.1%}")
print(f"Nodes kept: {nb.node_fraction(G, backbone):.1%}")

Significance options: multiple-testing correction and signed backbones

# Correct p-values for the number of edges tested (Bonferroni, Holm, BH/FDR, BY)
backbone = nb.threshold_filter(scored, "disparity_pvalue", 0.05, mtc="bh")

# Signed backbone: keep significantly strong (+1) and significantly weak (-1)
# edges under a two-tailed test; read direction from the "sign" attribute
signed = nb.disparity_filter(G, signed=True)
strong = nb.threshold_filter(signed, "disparity_pvalue", 0.05, mtc="holm")
positives = [(u, v) for u, v, d in strong.edges(data=True) if d["sign"] == 1]

Reporting a backbone (methods text and citations)

describe_backbone writes a methods paragraph for the backbone you extracted: the method and its null model, the parameters, the multiple-testing correction, the share of nodes, edges and weight kept, and the citations (including this package and its version). It is the counterpart of Backbone 3.0's narrative option.

print(nb.describe_backbone("disparity_filter", alpha=0.05, mtc="bh",
                           original=G, backbone=backbone))
print(nb.describe_backbone("disparity_filter", style="bibtex"))  # BibTeX entries

See the Validating a backbone tutorial for multiple-testing correction, method comparison, consensus and signed backbones end to end. To cite the package itself, use CITATION.cff.

Disparity filter visualization

Proximity-based scoring

# Score edges by Jaccard similarity of endpoint neighborhoods
scored = nb.jaccard_backbone(G)

# Keep only the top 20% most structurally embedded edges
backbone = nb.fraction_filter(scored, "jaccard", 0.2, ascending=False)

Bipartite backbone

B = nx.davis_southern_women_graph()
women_nodes = [n for n, d in B.nodes(data=True) if d["bipartite"] == 0]
scored = nb.sdsm(B, agent_nodes=women_nodes, projection="hyper")
backbone = nb.threshold_filter(scored, "sdsm_pvalue", 0.05, mode="below")

Projection weights follow the simple/hyper/ProbS/YCN formulations compared by Coscia & Rossi (2019) (arXiv:1906.09081). Their "hyperbolic" weight is 1/d(z) per shared artifact; pass hyper_projection(..., newman=True) (or projection="newman") for Newman's (2001) 1/(d(z) - 1) collaboration weight, which matches nx.bipartite.collaboration_weighted_projected_graph.

Every bipartite function also takes an agents x artifacts incidence matrix (NumPy, SciPy sparse or pandas) instead of a graph, as R backbone does. The incidence stays sparse and pairs are scored in blocks of agent rows:

import scipy.sparse as sp

M = sp.random_array((20_000, 5_000), density=0.01, format="csr")
M.data[:] = 1
backbone = nb.backbone_from_projection(M, method="sdsm", alpha=0.01)

Hypergraph backbones

Backbone a hypergraph (a collection of arbitrary-size hyperedges) directly:

# Parameter-free MDL backbone -- prunes nested/redundant hyperedges
# (Kirkley, Felippe, Malizia & Battiston, 2026)
H = [(1, 2, 3, 4), (1, 2, 3), (2, 3, 4), (8, 9)]
result = nb.mdl_hypergraph_backbone(H)          # method="auto" runs both greedy
print(result.backbone)            # [frozenset({1, 2, 3, 4}), frozenset({8, 9})]
print(result.compression_ratio)   # inverse compression ratio eta
# method="edge" (fastest single pass) or "node" are also available

# Statistically validated hypergraph (Musciotto, Battiston & Mantegna, 2021)
events = [(1, 2)] * 5 + [(3, 4)] * 100          # repeats = interaction counts
svh = nb.statistically_validated_hypergraph(events, alpha=0.05)

Interoperate with the higher-order ecosystem (all optional, lazily imported), or reuse the bipartite projection backbones via the incidence graph:

B, nodes = nb.hypergraph_to_bipartite(H)        # -> NetworkX bipartite graph
scored = nb.sdsm(B, agent_nodes=nodes)          # projection backbone of a hypergraph

nb.write_hif(H, "graph.hif")                    # HIF interchange (xgi/HNX/HGX/HAT)
edges = nb.from_xgi(xgi_hypergraph)             # xgi / hypernetx / hypergraphx / hat

Temporal networks

A network observed over time can be a dict of snapshots, a MultiGraph of timestamped events, or a MultiGraph of spans with start/end. The temporal module converts between the three forms and collapses any of them into one static weighted graph for the methods above:

M = nb.from_event_table(df)                       # pandas: source, target, time
weekly = nb.snapshots_from_events(M, freq="7D")   # bin events into snapshots
H = nb.flatten_temporal(M, aggregate="count")     # one weighted edge per pair
backbone = nb.threshold_filter(nb.disparity_filter(H), "disparity_pvalue", 0.05)

Temporal backbone scores (observation_fraction, persistence, backbone_stability, weight_trend) and kalman_backbone, which smooths per-step significance over time with a Kalman filter, return one scored static graph; a persistence HMM is on the roadmap.

Comparing multiple methods

backbones = {
    "disparity": nb.threshold_filter(nb.disparity_filter(G), "disparity_pvalue", 0.05),
    "mst": nb.boolean_filter(nb.maximum_spanning_tree_backbone(G), "mst_keep"),
}
results = nb.compare_backbones(G, backbones)

Dependencies

• Required: Python >= 3.12, networkx >= 3.4 (version floors match NetworkX's own)
• Optional: numpy >= 2.2, scipy >= 1.15 ([full]: some statistical methods, bipartite null models, SVH/SVC, doubly_stochastic_filter, local_path_index, KS measures) and matplotlib >= 3.10 ([viz]: visualization helpers and the docs gallery). Calling a function whose optional dependency is missing raises ImportError; the pure-Python methods work with NetworkX alone.
• pandas (optional, lazily imported): data-frame input (to_graph, bipartite incidence tables), pandas event tables (from_event_table, to_event_table), and frequency strings such as freq="1D" in the temporal module. Install it separately (pip install pandas). transform_weights accepts scikit-learn transformers by duck typing, so scikit-learn is never required.
• Backends (optional): install a NetworkX backend such as nx-parallel and pass backend="parallel" (see the backends user-guide page).
• Hypergraph interop (optional, lazily imported): xgi >= 0.9.1, hypernetx >= 2.3.10, hypergraphx >= 1.7.7, HypergraphAnalysisToolbox >= 1.1.18 (extras [xgi], [hypernetx], [hypergraphx], [hat], or all four with [interop])

Testing

pip install -e ".[dev]"
pytest --doctest-modules nx_backbone tests   # tests + docstring examples
ruff check nx_backbone tests && ruff format --check nx_backbone tests

Roadmap

Planned work, open gaps, and recently completed milestones are tracked in the roadmap (source).

Visualization gallery

Backbone visualizations in the docs are generated with Sphinx Gallery from example scripts under docs/examples/.

Build docs (including the graph comparison gallery and function-linked visualizations):

pip install -e ".[docs]"
sphinx-build -b html docs docs/_build/html

References

Key papers behind the implemented methods:

• Coscia, M. & Neffke, F. M. (2017). Network backboning with noisy data. Proc. IEEE ICDE, 425-436.
• Coscia, M. & Rossi, L. (2019). The impact of projection and backboning on network topologies. Proc. IEEE/ACM ASONAM. arXiv:1906.09081.
• Dianati, N. (2016). Unwinding the hairball graph: Pruning algorithms for weighted complex networks. Physical Review E, 93, 012304.
• Foti, N. J., Hughes, J. M., & Rockmore, D. N. (2011). Nonparametric sparsification of complex multiscale networks. PLoS One, 6(2), e16431.
• Girvan, M., & Newman, M. E. J. (2002). Community structure in social and biological networks. PNAS, 99(12), 7821-7826.
• Godard, K., & Neal, Z. P. (2022). fastball: A fast algorithm to sample bipartite graphs with fixed degree sequences. J. Complex Networks, 10(6), cnac049.
• Gemmetto, V., Cardillo, A., & Garlaschelli, D. (2017). Irreducible network backbones: unbiased graph filtering via maximum entropy. arXiv:1706.00230.
• Grady, D., Thiemann, C., & Brockmann, D. (2012). Robust classification of salient links in complex networks. Nature Communications, 3, 864.
• Hamann, M., Lindner, G., Meyerhenke, H., Staudt, C. L., and Wagner, D. (2016). Structure-Preserving Sparsification Methods for Social Networks. Social Network Analysis and Mining, 6, 22.
• Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Journal of Basic Engineering, 82(1), 35-45.
• Marcaccioli, R., & Livan, G. (2019). A Pólya urn approach to information filtering in complex networks. Nature Communications, 10, 745.
• Simas, T., Correia, R. B., & Rocha, L. M. (2021). The distance backbone of complex networks. J. Complex Networks, 9(6), cnab021.
• Newman, M. E. J. (2001). Scientific collaboration networks. II. Shortest paths, weighted networks, and centrality. Physical Review E, 64, 016132.
• Neal, Z. P. (2014). The backbone of bipartite projections. Social Networks, 39, 84-97.
• Neal, Z. P., Domagalski, R., & Sagan, B. (2021). Comparing alternatives to the fixed degree sequence model for extracting the backbone of bipartite projections. Scientific Reports, 11, 23929.
• Neal, Z. P. (2022). backbone: An R package to extract network backbones. PLoS One, 17(5), e0269137.
• Neal, Z. P. (2026). Backbone 3.0: An R package for extracting network backbones. PLoS One, 21, e0349258.
• Neal, Z. P., & Neal, J. W. (2023). Stochastic Degree Sequence Model with Edge Constraints (SDSM-EC) for Backbone Extraction. Complex Networks 12, 127-136.
• Radicchi, F., Ramasco, J. J., & Fortunato, S. (2011). Information filtering in complex weighted networks. Physical Review E, 83(4), 046101.
• Rauch, H. E., Tung, F., & Striebel, C. T. (1965). Maximum likelihood estimates of linear dynamic systems. AIAA Journal, 3(8), 1445-1450.
• Saracco, F., Di Clemente, R., Gabrielli, A., & Squartini, T. (2015). Randomizing bipartite networks: the case of the World Trade Web. Scientific Reports, 5, 10595.
• Satuluri, V., Parthasarathy, S., & Ruan, Y. (2011). Local graph sparsification for scalable clustering. SIGMOD, 721-732.
• Serrano, M. A., Boguna, M., & Vespignani, A. (2009). Extracting the multiscale backbone of complex weighted networks. PNAS, 106(16), 6483-6488.
• Van Nuffel, N. (2007). Determination of the number of significant flows in origin-destination specific analysis: the case of commuting in Flanders. Regional Studies, 41(4), 509-524.
• Van Nuffel, N., Derudder, B., & Witlox, F. (2010). Even important connections are not always meaningful: on the use of a polarisation measure in a typology of European cities in air transport networks. Tijdschrift voor Economische en Sociale Geografie, 101(3), 333-348.
• Weaver, J. C. (1954). Crop-combination regions in the Middle West. Geographical Review, 44(2), 175-200.
• Yildirim, M. A., & Coscia, M. (2014). Using random walks to generate associations between objects. PLoS One, 9(8), e104813.
• Zhang, X., Zhang, Z., Zhao, H., Wang, Q., & Zhu, J. (2014). Extracting the globally and locally adaptive backbone of complex networks. PLoS One, 9(6), e100428.
• Zhou, T., Ren, J., Medo, M., & Zhang, Y.-C. (2007). Bipartite network projection and personal recommendation. Physical Review E, 76, 046115.
• Yassin, A., Haidar, A., Cherifi, H., Seba, H., & Togni, O. (2023). An evaluation tool for backbone extraction techniques in weighted complex networks. Scientific Reports, 13, 17000.
• Yassin A., Cherifi, H., Seba, H., & Togni, O. (2025). Backbone extraction through statistical edge filtering: A comparative study. PLoS One, 20(1): e0316141.
• Yassin A., Cherifi, H., Seba, H., & Togni, O. (2025). Exploring weighted network backbone extraction: A comparative analysis of structural techniques. PLoS One, 20(5): e0322298.

Other libraries and datasets:

• Yassin, A., Haidar, A., Cherifi, H., Seba, H., & Togni, O. (2023). netbone.
• Yassin, A., et al. (2025). structural-backbone-methods-comparison.
• Neal, Z. (2022). backbone.
• Chrol, B. & Bojanowski, M. (2018). Proximity-based Methods for Link Prediction.

License

BSD 3-Clause License. See LICENSE for details.