Filters#

Examples in this module use nx.les_miserables_graph() and nx.davis_southern_women_graph(). Complexity classes are provided in each function docstring.

Filtering utilities for backbone extraction.

After a backbone method annotates edges (or nodes) with scores or p-values, these functions extract the final subgraph.

networkx_backbone.multigraph_to_weighted(G, weight='weight', edge_type_attr=None)[source]#

Convert a MultiGraph/MultiDiGraph into a weighted simple graph.

Parallel edges between the same node pair are collapsed into a single weighted edge.

Parameters:

  • G (graph) – A NetworkX graph. If G is a MultiGraph or MultiDiGraph, parallel edges are aggregated. For simple graphs, a copy is returned with missing weights filled as 1.

  • weight (string, optional (default="weight")) – Edge attribute name used to store the aggregated weight.

  • edge_type_attr (string or None, optional (default=None)) – If provided, weight is the count of distinct values of this edge attribute among parallel edges. If missing on all parallel edges, falls back to the number of parallel edges.

Returns:

H – nx.Graph for undirected input and nx.DiGraph for directed input. Each collapsed edge includes:

  • weight: aggregated weight

  • "edge_count": number of parallel edges collapsed

  • "edge_type_count": number of distinct edge types (only when edge_type_attr is provided)

Return type:

graph

Examples

>>> import networkx as nx

>>> from networkx_backbone import multigraph_to_weighted
>>> B = nx.davis_southern_women_graph()
>>> MG = nx.MultiGraph()
>>> MG.add_nodes_from(B.nodes(data=True))
>>> u, v = next(iter(B.edges()))
>>> _ = MG.add_edge(u, v, edge_type="attendance_a")
>>> _ = MG.add_edge(u, v, edge_type="attendance_b")
>>> H = multigraph_to_weighted(MG, edge_type_attr="edge_type")
>>> H[u][v]["weight"]
2

Computational complexity estimate is O(m) time and O(n + m) space.

networkx_backbone.threshold_filter(G, score, threshold, mode='below', filter_on='edges', include_all_nodes=True)[source]#

Retain edges or nodes whose score passes a threshold test.

Parameters:

  • G (graph) – A NetworkX graph with a computed score attribute on edges or nodes.

  • score (string) – Attribute name to filter on.

  • threshold (float) – Cutoff value.

  • mode ({"below", "above"}, optional (default="below")) – "below" keeps elements with score < threshold (typical for p-values). "above" keeps elements with score >= threshold (typical for salience or importance scores).

  • filter_on ({"edges", "nodes"}, optional (default="edges")) – Whether to filter edges or nodes.

  • include_all_nodes (bool, optional (default=True)) –

    Controls isolate retention in the output.

    • If filter_on="edges" and True, all input nodes are kept. If False, only nodes incident to retained edges are kept.

    • If filter_on="nodes" and True, all retained nodes are kept even if isolated in the induced subgraph. If False, retained nodes with degree 0 are removed.

Returns:

H – Filtered subgraph of the same type as G. When filtering edges, all original nodes are preserved by default. When filtering nodes, only retained nodes and their mutual edges are preserved.

Return type:

graph

Raises:

ValueError – If mode is not "below" or "above", or if filter_on is not "edges" or "nodes".

Examples

>>> import networkx as nx

>>> from networkx_backbone import disparity_filter, threshold_filter
>>> G = nx.les_miserables_graph()
>>> H = disparity_filter(G)
>>> filtered = threshold_filter(H, "disparity_pvalue", 0.5)
>>> filtered.number_of_edges() <= H.number_of_edges()
True

Computational complexity estimate is O(n + m) time and O(n + m) space.

networkx_backbone.fraction_filter(G, score, fraction, ascending=True, filter_on='edges')[source]#

Retain the top or bottom fraction of edges or nodes by score.

Parameters:

  • G (graph) – A NetworkX graph with a computed score attribute.

  • score (string) – Attribute name to sort on.

  • fraction (float) – Fraction of elements to retain, in (0, 1].

  • ascending (bool, optional (default=True)) – If True, keep the elements with the smallest scores (e.g. lowest p-values). If False, keep the largest.

  • filter_on ({"edges", "nodes"}, optional (default="edges")) – Whether to filter edges or nodes.

Returns:

H – Filtered subgraph of the same type as G.

Return type:

graph

Raises:

ValueError – If fraction is not in (0, 1] or filter_on is invalid.

Examples

>>> import networkx as nx

>>> from networkx_backbone import disparity_filter, fraction_filter
>>> G = nx.les_miserables_graph()
>>> H = disparity_filter(G)
>>> filtered = fraction_filter(H, "disparity_pvalue", 0.5)
>>> filtered.number_of_edges() <= H.number_of_edges()
True

Computational complexity estimate is O(m log m) time and O(n + m) space.

networkx_backbone.boolean_filter(G, score)[source]#

Retain edges whose boolean score attribute is truthy.

Parameters:

  • G (graph) – A NetworkX graph.

  • score (string) – Edge attribute name (should contain boolean values).

Returns:

H – A new graph of the same type as G containing only edges for which data[score] is truthy. All original nodes are preserved.

Return type:

graph

Examples

>>> import networkx as nx

>>> from networkx_backbone import boolean_filter, global_threshold_filter
>>> G = nx.les_miserables_graph()
>>> scored = global_threshold_filter(G, threshold=2)
>>> H = boolean_filter(scored, "global_threshold_keep")
>>> H.number_of_edges() <= scored.number_of_edges()
True

Computational complexity estimate is O(n + m) time and O(n + m) space.

networkx_backbone.consensus_backbone(*backbones)[source]#

Return the intersection of multiple backbone graphs.

An edge is in the consensus backbone if and only if it appears in every input backbone. Only nodes that are endpoints of consensus edges are retained.

Parameters:

*backbones (graph) – Two or more backbone graphs (must share the same node identifiers).

Returns:

H – A new graph of the same type as the first backbone, containing only edges present in every input.

Return type:

graph

Raises:

ValueError – If fewer than 2 backbones are provided.

Examples

>>> import networkx as nx

>>> from networkx_backbone import (
...     consensus_backbone,
...     jaccard_backbone,
...     cosine_backbone,
...     fraction_filter,
... )
>>> G = nx.les_miserables_graph()
>>> B1 = fraction_filter(jaccard_backbone(G), "jaccard", 0.3, ascending=False)
>>> B2 = fraction_filter(cosine_backbone(G), "cosine", 0.3, ascending=False)
>>> H = consensus_backbone(B1, B2)
>>> H.number_of_edges() <= min(B1.number_of_edges(), B2.number_of_edges())
True

Computational complexity estimate is O(km) time and O(m) space.