Filters#

Examples in this module use nx.les_miserables_graph() and nx.davis_southern_women_graph(). Complexity classes are provided in each function docstring. From a hairball to a backbone, end to end shows how to choose the threshold and the multiple-testing correction (mtc).

Filtering utilities for backbone extraction.

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

nx_backbone.multigraph_to_weighted(G, weight='weight', edge_type_attr=None, aggregate='count')[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:

Ggraph: 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.
weightstring, optional (default=”weight”): Edge attribute name used to store the aggregated weight.
edge_type_attrstring 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. Only used with aggregate="count".
aggregate{“count”, “sum”, “max”, “min”, “mean”}, optional (default=”count”): How parallel edges are combined. "count" sets the weight to the number of parallel edges (or of distinct edge types). The other options combine the existing weight attribute of the parallel edges, treating a missing weight as 1.

Returns:

Hgraph

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)

Raises:

ValueError: If aggregate is not recognized.

Examples

>>> import networkx as nx
>>> from nx_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

Sum existing weights instead of counting edges:

>>> M = nx.MultiGraph([(0, 1, {"weight": 10}), (0, 1, {"weight": 20})])
>>> multigraph_to_weighted(M, aggregate="sum")[0][1]["weight"]
30

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

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

Retain edges or nodes whose score passes a threshold test.

Parameters:

Ggraph

A NetworkX graph with a computed score attribute on edges or nodes.

scorestring

Attribute name to filter on.

thresholdfloat

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_nodesbool, 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.

mtcstring, optional (default=”none”)

Multiple-testing correction applied to score values before thresholding (see adjust_pvalues()). Only valid with mode="below" (p-values). Default "none" leaves scores unchanged.

Returns:

Hgraph: 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. Graph, node, and edge attributes are copied (as are edge keys of multigraphs). Elements without the score attribute (or with a NaN score) are dropped.

Raises:

ValueError: If mode is not "below" or "above", if filter_on is not "edges" or "nodes", or if mtc is used with mode="above".

See also

fraction_filter: Keep a fixed share of elements instead.
boolean_filter: Keep edges flagged by a *_keep attribute.
adjust_pvalues: The multiple-testing corrections behind mtc.

Examples

>>> import networkx as nx

>>> from nx_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.

nx_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:

Ggraph: A NetworkX graph with a computed score attribute.
scorestring: Attribute name to sort on.
fractionfloat: Fraction of elements to retain, in (0, 1].
ascendingbool, 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:

Hgraph: Filtered subgraph of the same type as G. Elements without the score attribute are never kept; the fraction is taken of the scored elements. Ties are broken by input order.

Raises:

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

See also

threshold_filter: Keep elements passing a fixed cutoff instead.

Examples

>>> import networkx as nx

>>> from nx_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.

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

Retain edges whose boolean score attribute is truthy.

Parameters:

Ggraph: A NetworkX graph.
scorestring: Edge attribute name (should contain boolean values).

Returns:

Hgraph: A new graph of the same type as G containing only edges for which data[score] is truthy. All original nodes are preserved, along with graph, node, and edge attributes.

See also

threshold_filter: Filter on a numeric score.

Examples

>>> import networkx as nx

>>> from nx_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.

nx_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:

*backbonesgraph: Two or more backbone graphs (must share the same node identifiers).

Returns:

Hgraph: A new graph of the same type as the first backbone, containing only edges present in every input, with the edge, node, and graph attributes of the first backbone. Edges keep the order of the first backbone. Parallel edges of multigraphs are matched by node pair.

Raises:

ValueError: If fewer than 2 backbones are provided.

Examples

>>> import networkx as nx

>>> from nx_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.

nx_backbone.adjust_pvalues(pvalues, method='bh')[source]#

Apply a multiple-testing correction to a collection of p-values.

Reproduces R’s p.adjust for the methods used by Neal’s Backbone 3.0 mtc option, so statistical backbone p-values can be corrected for the number of edges tested before thresholding.

Parameters:

pvaluesiterable of float: The raw p-values.
methodstring, optional (default=”bh”): One of "none", "bonferroni", "holm" (step-down), "hochberg" (step-up), "bh"/"fdr" (Benjamini-Hochberg), or "by" (Benjamini-Yekutieli).

Returns:

adjustedlist of float: Adjusted p-values in the same order as the input, each in [0, 1]. Missing values (NaN) stay NaN and, as in R’s p.adjust, do not count toward the number of tests.

Raises:

ValueError: If method is not recognized.

References

[1]

Holm, S. (1979). A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics, 6(2), 65-70.

[2]

Hochberg, Y. (1988). A sharper Bonferroni procedure for multiple tests of significance. Biometrika, 75(4), 800-802.

[3]

Benjamini, Y., & Hochberg, Y. (1995). Controlling the false discovery rate. J. Royal Statistical Society B, 57(1), 289-300.

[4]

Benjamini, Y., & Yekutieli, D. (2001). The control of the false discovery rate in multiple testing under dependency. Annals of Statistics, 29(4), 1165-1188.

Examples

>>> from nx_backbone import adjust_pvalues
>>> adjust_pvalues([0.01, 0.02, 0.5], method="bonferroni")
[0.03, 0.06, 1.0]

nx_backbone.transform_weights(G, transformer, weight='weight', out=None)[source]#

Return a copy of G with transformed edge weights.

Applies transformer to the edge weights before scoring, for example a log, power, or Box-Cox transform. Transforming weights changes the hypothesis a statistical method tests: the disparity filter applied to log1p(w) tests whether the log-weights’ shares are uniform, not whether the weights’ shares are. Some methods give the same result for every increasing transform, some only for rescaling, and some for neither; see Weights, Units, and Transforms.

Parameters:

Gnetworkx.Graph or networkx.DiGraph: A weighted graph. Every edge needs a finite, real weight.
transformercallable or object with fit_transform or transform: Either an object with a scikit-learn style fit_transform method (or only transform, for one that is already fitted), which is called once with the weights as a column of shape (m, 1) in G.edges order and must return m values; or a plain callable such as math.log1p() or numpy.sqrt, which is called on each weight in turn. scikit-learn is not needed: any object with these methods works, and a plain callable needs neither NumPy nor scikit-learn.
weightstring, optional (default=”weight”): Edge attribute holding the weights to transform.
outstring or None, optional (default=None): Edge attribute that receives the transformed weights. None overwrites weight; another name keeps the original weights.

Returns:

Hgraph: A copy of G (same type) with the transformed weights in out. The neighbor order of every node is the same as in G, so methods that break ties by neighbor order behave as on G. The transform is appended to the list H.graph["weight_transforms"] as a dict with keys "transform" (a description of transformer), "weight" and "out"; describe_backbone() reports it.

Raises:

NetworkXError: If an edge has a missing, non-numeric, or non-finite weight.
NetworkXNotImplemented: If G is a multigraph. Collapse parallel edges first with multigraph_to_weighted().
TypeError: If transformer is neither callable nor has fit_transform or transform.
ValueError: If the transformer returns the wrong number of values, a non-finite value, or the same value for every edge although the weights differ (for example scikit-learn’s Normalizer, which scales each row, maps a column of weights to all ones).

Warns:

UserWarning: If the transform does not preserve the order of the weights (a larger weight gets a smaller value, or equal weights get different values), or if it maps different weights to the same value. Methods that only use the ranks of the weights change in either case.

See also

marginal_likelihood_filter: Count models take unit= for a change of unit instead of a transform.

Notes

The transformed weights are not checked for positivity; the statistical scorers reject non-positive weights themselves. Transforms that center or standardize (StandardScaler, PowerTransformer with its default standardize=True, QuantileTransformer with a normal output) produce negative weights.

Count-based null models (marginal_likelihood_filter(), ecm_filter(), noise_corrected_filter(), polya_filter()) treat weights as numbers of events, which a continuous transform does not preserve, and binning (for example KBinsDiscretizer) gives ordinal labels, not counts. To change the size of one count use their unit= argument instead.

Examples

>>> import math
>>> import networkx as nx
>>> from nx_backbone import disparity_filter, transform_weights
>>> G = nx.les_miserables_graph()
>>> H = transform_weights(G, math.log1p)
>>> round(H["Valjean"]["Javert"]["weight"], 4)
2.8904
>>> H.graph["weight_transforms"]
[{'transform': 'math.log1p', 'weight': 'weight', 'out': 'weight'}]
>>> scored = disparity_filter(H)

Any object with a scikit-learn style fit_transform works, such as a Box-Cox power transform without standardization:

>>> from sklearn.preprocessing import PowerTransformer
>>> pt = PowerTransformer(method="box-cox", standardize=False)
>>> H = transform_weights(G, pt, out="boxcox")

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