Measures

Examples in this module use nx.les_miserables_graph(). Complexity classes are provided in each function docstring. From a hairball to a backbone, end to end compares four backbones with compare_backbones() and a custom measure.

Evaluation measures for comparing backbones against their original network.

nx_backbone.node_fraction(original, backbone)

Compute the fraction of original nodes that appear in the backbone.

Only nodes that have at least one edge in the respective graph are counted. Isolated nodes are ignored.

Parameters:

originalgraph

The original NetworkX graph.

backbonegraph

The backbone NetworkX graph.

Returns:

fractionfloat

Fraction in [0, 1]. Returns 0.0 if original has no nodes with edges.

Examples

>>> import networkx as nx

>>> from nx_backbone import node_fraction
>>> G = nx.les_miserables_graph()
>>> H = G.edge_subgraph(list(G.edges())[:100]).copy()
>>> 0.0 < node_fraction(G, H) <= 1.0
True

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

nx_backbone.edge_fraction(original, backbone)

Compute the fraction of original edges preserved in the backbone.

Parameters:

originalgraph

The original NetworkX graph.

backbonegraph

The backbone NetworkX graph.

Returns:

fractionfloat

Fraction in [0, 1]. Returns 0.0 if original has no edges.

Examples

>>> import networkx as nx

>>> from nx_backbone import edge_fraction
>>> G = nx.les_miserables_graph()
>>> H = G.edge_subgraph(list(G.edges())[:100]).copy()
>>> 0.0 < edge_fraction(G, H) < 1.0
True

Computational complexity estimate is O(1) time and O(1) space.

nx_backbone.weight_fraction(original, backbone, weight='weight')

Compute the fraction of total edge weight preserved in the backbone.

Parameters:

originalgraph

The original NetworkX graph.

backbonegraph

The backbone NetworkX graph.

weightstring, optional (default=”weight”)

Edge attribute key used as the weight.

Returns:

fractionfloat

Fraction in [0, 1]. Returns 0.0 if original has zero total weight.

Examples

>>> import networkx as nx

>>> from nx_backbone import (
...     weight_fraction,
...     global_threshold_filter,
...     boolean_filter,
... )
>>> G = nx.les_miserables_graph()
>>> scored = global_threshold_filter(G, threshold=2)
>>> H = boolean_filter(scored, "global_threshold_keep")
>>> 0.0 < weight_fraction(G, H) <= 1.0
True

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

nx_backbone.reachability(G)

Compute the fraction of ordered node pairs joined by a path.

For a connected undirected graph (or a strongly connected directed graph) this is 1.0. For a graph with all isolated nodes this is 0.0. For a directed graph, a pair (i, j) counts only if j can be reached from i along edge directions. Graphs with fewer than two nodes have no pairs; their reachability is defined as 1.0.

Parameters:

Ggraph

A NetworkX graph.

Returns:

fractionfloat

Fraction in [0, 1] of ordered node pairs (i, j) for which a path exists.

Examples

>>> import networkx as nx

>>> from nx_backbone import reachability
>>> G = nx.les_miserables_graph()
>>> reachability(G)
1.0
>>> H = nx.Graph()
>>> H.add_nodes_from(G.nodes())
>>> reachability(H)
0.0

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

nx_backbone.ks_degree(original, backbone)

Compute the Kolmogorov-Smirnov statistic between degree distributions.

Parameters:

originalgraph

The original NetworkX graph.

backbonegraph

The backbone NetworkX graph.

Returns:

statisticfloat

KS statistic in [0, 1].

Examples

>>> import networkx as nx

>>> from nx_backbone import ks_degree, global_threshold_filter, boolean_filter
>>> G = nx.les_miserables_graph()
>>> H = boolean_filter(global_threshold_filter(G, threshold=2), "global_threshold_keep")
>>> 0.0 <= ks_degree(G, H) <= 1.0
True

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

nx_backbone.ks_weight(original, backbone, weight='weight')

Compute the Kolmogorov-Smirnov statistic between weight distributions.

Parameters:

originalgraph

The original NetworkX graph.

backbonegraph

The backbone NetworkX graph.

weightstring, optional (default=”weight”)

Edge attribute key used as the weight.

Returns:

statisticfloat

KS statistic in [0, 1].

Examples

>>> import networkx as nx

>>> from nx_backbone import ks_weight, global_threshold_filter, boolean_filter
>>> G = nx.les_miserables_graph()
>>> H = boolean_filter(global_threshold_filter(G, threshold=2), "global_threshold_keep")
>>> 0.0 <= ks_weight(G, H) <= 1.0
True

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

nx_backbone.compare_backbones(original, backbones, measures=None, weight='weight')

Compare multiple backbones on a set of evaluation measures.

Parameters:

originalgraph

The original NetworkX graph.

backbonesdict

Mapping {name: backbone_graph}.

measureslist of callable, optional

Each callable has signature (original, backbone) and returns a float. Defaults to [node_fraction, edge_fraction, weight_fraction].

weightstring, optional (default=”weight”)

Weight attribute, forwarded to every measure that accepts a weight keyword (such as weight_fraction() and ks_weight()).

Returns:

resultsdict

{backbone_name: {measure_name: value}}.

Examples

>>> import networkx as nx

>>> from nx_backbone import (
...     compare_backbones,
...     edge_fraction,
...     global_threshold_filter,
...     boolean_filter,
... )
>>> G = nx.les_miserables_graph()
>>> H = boolean_filter(global_threshold_filter(G, threshold=2), "global_threshold_keep")
>>> results = compare_backbones(G, {"threshold": H}, measures=[edge_fraction])
>>> "edge_fraction" in results["threshold"]
True

Computational complexity estimate is O(b * C) time and O(b * q) space.