Measures#

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

Evaluation measures for comparing backbones against their original network.

networkx_backbone.node_fraction(original, backbone)[source]#

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:

  • original (graph) – The original NetworkX graph.

  • backbone (graph) – The backbone NetworkX graph.

Returns:

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

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.edge_fraction(original, backbone)[source]#

Compute the fraction of original edges preserved in the backbone.

Parameters:

  • original (graph) – The original NetworkX graph.

  • backbone (graph) – The backbone NetworkX graph.

Returns:

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

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.weight_fraction(original, backbone, weight='weight')[source]#

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

Parameters:

  • original (graph) – The original NetworkX graph.

  • backbone (graph) – The backbone NetworkX graph.

  • weight (string, optional (default="weight")) – Edge attribute key used as the weight.

Returns:

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

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.reachability(G)[source]#

Compute the fraction of node pairs that can communicate.

For a connected graph this is 1.0. For a graph with all isolated nodes this is 0.0.

Parameters:

G (graph) – A NetworkX graph.

Returns:

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

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.ks_degree(original, backbone)[source]#

Compute the Kolmogorov-Smirnov statistic between degree distributions.

Parameters:

  • original (graph) – The original NetworkX graph.

  • backbone (graph) – The backbone NetworkX graph.

Returns:

statistic – KS statistic in [0, 1].

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.ks_weight(original, backbone, weight='weight')[source]#

Compute the Kolmogorov-Smirnov statistic between weight distributions.

Parameters:

  • original (graph) – The original NetworkX graph.

  • backbone (graph) – The backbone NetworkX graph.

  • weight (string, optional (default="weight")) – Edge attribute key used as the weight.

Returns:

statistic – KS statistic in [0, 1].

Return type:

float

Examples

>>> import networkx as nx

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

networkx_backbone.compare_backbones(original, backbones, measures=None, weight='weight')[source]#

Compare multiple backbones on a set of evaluation measures.

Parameters:

  • original (graph) – The original NetworkX graph.

  • backbones (dict) – Mapping {name: backbone_graph}.

  • measures (list of callable, optional) – Each callable has signature (original, backbone) and returns a float. Defaults to [node_fraction, edge_fraction, weight_fraction].

  • weight (string, optional (default="weight")) – Weight attribute (forwarded to weight_fraction()).

Returns:

results – {backbone_name: {measure_name: value}}.

Return type:

dict

Examples

>>> import networkx as nx

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