Structural Backbone Methods
===========================

This tutorial demonstrates the structural methods, which use topological
properties of the network to identify important edges.

.. seealso::

   :ref:`sphx_glr_auto_examples_structural_proximity_plot_structural_proximity_tutorial.py`,
   a narrative tutorial with figures on what each structural method
   guarantees and when to prefer one to a significance test.

Setup
-----

::

    import networkx as nx
    import nx_backbone as nb

    G = nx.les_miserables_graph()

    print(f"Original: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges")

Simple filters
--------------

**Global threshold**: Keep edges whose weight meets a minimum::

    scored = nb.global_threshold_filter(G, threshold=1.0)
    backbone = nb.boolean_filter(scored, "global_threshold_keep")
    print(f"Global threshold: {backbone.number_of_edges()} edges")

**Strongest N ties**: Keep each node's N strongest edges (edges tied with
the N-th strongest are kept too, so the result does not depend on edge
order)::

    scored = nb.strongest_n_ties(G, n=2)
    backbone = nb.boolean_filter(scored, "strongest_n_ties_keep")
    print(f"Strongest 2 ties: {backbone.number_of_edges()} edges")

**Global sparsification** (Satuluri et al., 2011): Keep the globally
strongest fraction of edges::

    scored = nb.global_sparsification(G, s=0.4)
    backbone = nb.boolean_filter(scored, "global_sparsification_keep")
    print(f"Global sparsification (40%): {backbone.number_of_edges()} edges")

Linkage and centrality filters
------------------------------

**Primary linkage analysis** (Nystuen & Dacey, 1961): Keep each node's
strongest outgoing edge::

    scored = nb.primary_linkage_analysis(G)
    backbone = nb.boolean_filter(scored, "primary_linkage_keep")
    print(f"Primary linkage: {backbone.number_of_edges()} edges")

**Edge betweenness filter** (Girvan & Newman, 2002): Keep edges with the
highest edge-betweenness centrality::

    scored = nb.edge_betweenness_filter(G, s=0.3)
    backbone = nb.boolean_filter(scored, "edge_betweenness_keep")
    print(f"Edge betweenness (30%): {backbone.number_of_edges()} edges")

**Node degree filter**: Keep only nodes whose degree meets a threshold::

    scored = nb.node_degree_filter(G, min_degree=2)
    backbone = nb.boolean_filter(scored, "node_degree_keep")
    print(f"Node degree (>=2): {backbone.number_of_nodes()} nodes")

Shortest-path methods
---------------------

**High salience skeleton** (Grady et al., 2012): Each edge receives a
salience score -- the fraction of shortest-path trees that include it.
Edges with high salience are consistently important for communication::

    H = nb.high_salience_skeleton(G)

    # Filter to keep edges with salience above 0.5
    backbone = nb.threshold_filter(H, "salience", 0.5, mode="above")
    print(f"High salience (>0.5): {backbone.number_of_edges()} edges")

**Metric backbone** (Simas et al., 2021): Keeps only edges that lie on
shortest paths (using the inverse of weight as distance). Always preserves
connectivity::

    scored = nb.metric_backbone(G)
    backbone = nb.boolean_filter(scored, "metric_keep")
    print(f"Metric backbone: {backbone.number_of_edges()} edges")
    print(f"Connected: {nx.is_connected(backbone)}")

**Ultrametric backbone** (Simas et al., 2021): Similar to metric backbone
but uses minimax paths instead of shortest paths::

    scored = nb.ultrametric_backbone(G)
    backbone = nb.boolean_filter(scored, "ultrametric_keep")
    print(f"Ultrametric backbone: {backbone.number_of_edges()} edges")

Normalization
-------------

**Doubly stochastic filter** (Slater, 2009): Normalizes the weight matrix
so that each row and column sums to 1 using Sinkhorn-Knopp iteration. Edges
with high normalized weight are important. Slater's second stage adds edges in
descending ``ds_weight`` order until the backbone is connected and flags them
as ``ds_keep``::

    H = nb.doubly_stochastic_filter(G)

    # Filter: Slater's connectivity stage
    backbone = nb.boolean_filter(H, "ds_keep")
    print(f"Doubly stochastic (connected): {backbone.number_of_edges()} edges")

    # Or cut the doubly-stochastic weight yourself
    backbone = nb.threshold_filter(H, "ds_weight", 0.1, mode="above")
    print(f"Doubly stochastic (>0.1): {backbone.number_of_edges()} edges")

Sinkhorn-Knopp does not converge on many sparse graphs, including this one: a
graph with several leaves on one node has no doubly stochastic scaling, and
the filter warns.  ``smoothing`` adds a small pseudocount to every off-diagonal
cell first, which makes the iteration converge.  Keep it small relative to the
weights, since it spreads each row's unit sum over every node::

    H = nb.doubly_stochastic_filter(G, smoothing=1e-4)
    backbone = nb.boolean_filter(H, "ds_keep")
    print(f"Doubly stochastic (smoothed): {backbone.number_of_edges()} edges")

On Les Misérables this keeps 220 edges, against 187 without smoothing.

Index-based
-----------

**H-backbone** (Zhang et al., 2018): Uses an h-index inspired criterion
to identify important edges::

    scored = nb.h_backbone(G)
    backbone = nb.boolean_filter(scored, "h_backbone_keep")
    print(f"H-backbone: {backbone.number_of_edges()} edges")

Community-based
---------------

**Modularity backbone** (Rajeh et al., 2022): Computes a vitality score for
each node based on how much removing it changes the network's modularity.
Use the boolean keep flag to extract retained edges::

    scored = nb.modularity_backbone(G)
    backbone = nb.boolean_filter(scored, "modularity_keep")
    print(f"Modularity backbone: {backbone.number_of_nodes()} nodes")

Constrained methods
-------------------

**Planar maximally filtered graph** (Tumminello et al., 2005): Greedily adds
edges from heaviest to lightest while maintaining planarity::

    scored = nb.planar_maximally_filtered_graph(G)
    backbone = nb.boolean_filter(scored, "pmfg_keep")
    print(f"PMFG: {backbone.number_of_edges()} edges")

**Maximum spanning tree**: Wrapper around NetworkX's MST algorithm.
Always produces a connected tree with exactly N-1 edges::

    scored = nb.maximum_spanning_tree_backbone(G)
    backbone = nb.boolean_filter(scored, "mst_keep")
    print(f"MST: {backbone.number_of_edges()} edges")
    print(f"Connected: {nx.is_connected(backbone)}")

Comparing structural methods
-----------------------------

::

    backbones = {
        "metric": nb.boolean_filter(nb.metric_backbone(G), "metric_keep"),
        "ultrametric": nb.boolean_filter(nb.ultrametric_backbone(G), "ultrametric_keep"),
        "h_backbone": nb.boolean_filter(nb.h_backbone(G), "h_backbone_keep"),
        "global_sparsification": nb.boolean_filter(
            nb.global_sparsification(G, s=0.4), "global_sparsification_keep"
        ),
        "edge_betweenness": nb.boolean_filter(
            nb.edge_betweenness_filter(G, s=0.3), "edge_betweenness_keep"
        ),
        "pmfg": nb.boolean_filter(nb.planar_maximally_filtered_graph(G), "pmfg_keep"),
        "mst": nb.boolean_filter(nb.maximum_spanning_tree_backbone(G), "mst_keep"),
    }

    results = nb.compare_backbones(G, backbones)
    for name, metrics in results.items():
        ef = metrics["edge_fraction"]
        nf = metrics["node_fraction"]
        print(f"{name:15s}: edges={ef:.1%}, nodes={nf:.1%}")