Hypergraph Methods#

Methods that operate directly on hypergraphs (collections of arbitrary-size hyperedges) rather than on dyadic graphs. Inputs are plain iterables of hyperedges (each hyperedge an iterable of node labels); the backbone is returned as a list of frozenset hyperedges inside a HypergraphBackbone result.

The mdl_hypergraph_backbone() method implements the parameter-free, information-theoretic (minimum description length) backbone of Kirkley, Felippe, Malizia & Battiston (2026), which prunes nested and redundant hyperedges and naturally extends to weighted hypergraphs. local_mdl_hypergraph_backbone() is its local variant (Appendix E of the paper), which backbones each node’s neighborhood separately.

For a narrative walk-through with figures, see Hypergraph backbones: keeping the groups that matter; for short code recipes, see Hypergraph Backbones.

Hypergraph backbone methods.

These methods operate directly on hypergraphs (collections of hyperedges, where each hyperedge is a set of nodes of arbitrary size) rather than on dyadic graphs.

A hyperedge is given as any iterable of node labels; a hypergraph is an iterable of hyperedges, for example [(1, 2, 3), (2, 4), (1, 2, 3, 5)]. NetworkX has no native hypergraph type, so inputs and outputs use plain Python collections (the backbone is returned as a list of frozenset hyperedges).

Methods#

mdl_hypergraph_backbone: Parameter-free information-theoretic (MDL) backbone that prunes nested and redundant hyperedges (Kirkley, Felippe, Malizia & Battiston, 2026).
local_mdl_hypergraph_backbone: Local variant that backbones each node neighborhood separately and aggregates the results (Kirkley et al., 2026, Appendix E).
hypergraph_compression_ratio: Inverse compression ratio eta achieved by the MDL backbone.
intersection_graph: Graph linking hyperedges that share at least one node.

nx_backbone.mdl_hypergraph_backbone(hyperedges, weights=None, gamma=1.0, prior='poisson', method='auto')[source]#

Extract a hypergraph backbone via minimum description length (MDL).

Implements the parameter-free information-theoretic backboning method of Kirkley, Felippe, Malizia & Battiston [1]. The backbone B is a subset of hyperedges (“parents”) chosen so that the remaining “child” hyperedges can be cheaply reconstructed from a parent they overlap, exploiting the nested and redundant structure unique to higher-order networks. The optimal backbone minimizes the two-part description length L(G, B) = L(B) + L(G|B) (Eqs (1)-(6)); equivalently it maximizes the total parent–child reduced mutual information (Eq. (12)).

The method is fully nonparametric for unweighted hypergraphs. Edge weights are incorporated through an empirical-Bayes prior with a single knob gamma trading off weight against topology (Sec. III).

Parameters:

hyperedgesiterable of iterables: The hypergraph. Each hyperedge is an iterable of node labels (treated as a set; repeated nodes within a hyperedge are ignored). Duplicate hyperedges are merged.
weightsiterable of numbers or None, optional (default=None): Optional per-hyperedge weights (each >= 1), parallel to hyperedges. None means an unweighted hypergraph.
gammafloat, optional (default=1.0): Weight/topology trade-off in (0, 1] (Eq. (14)). gamma=1 ignores weights (recovers the unweighted backbone); gamma -> 0 makes it increasingly costly to leave a high-weight hyperedge out of the backbone. Ignored when weights is None.
prior{“poisson”, “geometric”}, optional (default=”poisson”): Weight prior family (Eqs (16)-(17)). Ignored when weights is None.
method{“auto”, “edge”, “node”}, optional (default=”auto”): Greedy optimizer (Kirkley et al. 2026, Appendix D). "edge" adds parent–child links by decreasing gain; "node" adds backbone parents by decreasing total gain; "auto" runs both and keeps the lower description length (the procedure used in [1]).

Returns:

resultHypergraphBackbone: The backbone hyperedges, the parent–child assignment, and compression diagnostics (see HypergraphBackbone).

Raises:

ValueError: If gamma is not in (0, 1], prior is unknown, weights has the wrong length or contains a value < 1, or method is unsupported.

See also

hypergraph_compression_ratio: Only the compression ratio eta.
maximal_hyperedges: Purely set-inclusion (toplex) pruning.
statistically_validated_hypergraph: Statistical hyperedge filtering.

Notes

Exact minimization is combinatorial; this uses the greedy heuristics of [1], which forms a maximum-reward partition of the intersection graph into disjoint stars (each child attached to a single parent). On small inputs the greedy compression matches exhaustive search.

References

[1] (1,2,3)

Kirkley, A., Felippe, H., Malizia, F., & Battiston, F. (2026). Hypergraph backboning. arXiv:2606.00893.

Examples

>>> from nx_backbone import mdl_hypergraph_backbone
>>> # A 4-node hyperedge with two nested (redundant) sub-hyperedges.
>>> G = [(1, 2, 3, 4), (1, 2, 3), (2, 3, 4), (8, 9)]
>>> result = mdl_hypergraph_backbone(G)
>>> frozenset({1, 2, 3, 4}) in result.backbone
True
>>> result.compression_ratio <= 1.0
True

Computational complexity estimate is O(sum_i \|G_i\|^2 + P log P) time and O(m + P) space.

nx_backbone.local_mdl_hypergraph_backbone(hyperedges, weights=None, gamma=1.0, prior='poisson', aggregation='majority', method='auto')[source]#

Extract the local (per-node neighborhood) MDL hypergraph backbone.

The local variant of mdl_hypergraph_backbone() from Appendix E of Kirkley, Felippe, Malizia & Battiston [1], the higher-order analogue of the disparity filter. Each node i has a neighborhood G_i = {e in G : i in e}, the hyperedges containing it. The MDL objective is minimized on every neighborhood separately, “considered in isolation” (Eq. (E1)),

\[B_i^* = \arg\min_{B_i \subseteq G_i} \mathcal{L}(G_i, B_i),\]

and the neighborhood backbones B_i* are combined into one backbone B^(local) by an aggregation rule. Because each hyperedge is judged only against the other hyperedges of its own nodes, the backbone keeps hyperedges that are informative locally even when the global backbone encodes them as children of a hyperedge elsewhere; local backbones are therefore denser and compress less than the global one [1].

Parameters:

hyperedgesiterable of iterables

The hypergraph. Each hyperedge is an iterable of node labels (treated as a set). Duplicate hyperedges are merged.

weightsiterable of numbers or None, optional (default=None)

Optional per-hyperedge weights (each >= 1), parallel to hyperedges. As in [1], the weighted objective L_w (Eq. (13)) then replaces L in every neighborhood.

gammafloat, optional (default=1.0)

Weight/topology trade-off in (0, 1]; see mdl_hypergraph_backbone(). Ignored when weights is None.

prior{“poisson”, “geometric”}, optional (default=”poisson”)

Weight prior family. Ignored when weights is None.

aggregation{“majority”, “union”, “all”}, optional (default=”majority”)

How the neighborhood backbones are combined. A hyperedge e is kept if it belongs to B_i* for

"union": at least one of its nodes (Eq. (E2)); every node then stays in the backbone, but the backbone tends to be dense;
"majority": at least half of its nodes (the rule used for Table II of [1]; see Notes);
"all": every one of its nodes (the most conservative rule, often very sparse).

method{“auto”, “edge”, “node”}, optional (default=”auto”)

Greedy optimizer applied to each neighborhood; see mdl_hypergraph_backbone().

Returns:

resultHypergraphBackbone: The local backbone B^(local) (in input order) with description_length = Eq. (E3), baseline_description_length = sum_i L(G_i, G_i) and compression_ratio = eta^(local) (Eq. (E4)). Per-node results are in local_backbones (each B_i*) and local_description_lengths (each L(G_i, B_i*)); aggregation records the rule. assignment is empty, since there is no single global parent–child partition.

Raises:

ValueError: If aggregation is unknown, or for any invalid argument of mdl_hypergraph_backbone().

See also

mdl_hypergraph_backbone: The global MDL backbone.
disparity_filter: The dyadic local backbone this generalises.

Notes

Every hyperedge of G_i contains i, so all pairs of hyperedges in a neighborhood overlap and any non-empty subset of G_i is a valid backbone of it. The neighborhood objectives involve O(sum_i |G_i|^2) hyperedge pairs, as many as the global intersection graph is built from.

Appendix E of [1] leaves a few details implicit; this implementation makes the following choices.

“Considered in isolation” is read literally: the node count N, the number of distinct orders L and, for weighted input, the mean weight of the empirical-Bayes prior are those of G_i, not of G.
Majority means at least half of a hyperedge’s nodes. The paper notes that, with the union rule, the majority rule is “consistent with the disparity filter convention for pairwise edges in which the edge is kept […] if it belongs to either node’s neighborhood backbone”; for a two-node hyperedge only the at-least-half reading does that.
In Eq. (E3), L(G_i, B_i* ∩ B^(local)) assigns each remaining hyperedge of G_i to the parent in B_i* ∩ B^(local) that encodes it most cheaply. If that intersection is empty (possible only under "majority" or "all"), the neighborhood is charged its uncompressed cost L(G_i, G_i).
The denominator L^(local)(G, G) of Eq. (E4) is taken as sum_i L(G_i, G_i), the cost with no compression in any neighborhood (read literally, B_i* ∩ G = B_i* would make eta^(local) identically 1 under the union rule). With the union rule eta^(local) <= 1; with "majority" or "all" it can exceed 1 when dropping a neighborhood’s parents forces costlier encodings of its remaining hyperedges.

References

[1] (1,2,3,4,5)

Kirkley, A., Felippe, H., Malizia, F., & Battiston, F. (2026). Hypergraph backboning. arXiv:2606.00893.

Examples

A core hyperedge {0, ..., 5} with two nested sub-hyperedges and two “satellites”, each joining four core nodes to three peripheral nodes of its own. The global backbone encodes the satellite {0, 1, 2, 3, 6, 7, 8} as a child, but it is the only hyperedge in the neighborhoods of nodes 6, 7 and 8, so the local backbone keeps it (while still pruning the nested sub-hyperedges):

>>> from nx_backbone import (
...     local_mdl_hypergraph_backbone,
...     mdl_hypergraph_backbone,
... )
>>> G = [
...     (0, 1, 2, 3, 4, 5),
...     (0, 1, 2, 3, 4),
...     (0, 1, 2, 3, 5),
...     (0, 1, 2, 3, 6, 7, 8),
...     (2, 3, 4, 5, 9, 10, 11),
... ]
>>> satellite = frozenset({0, 1, 2, 3, 6, 7, 8})
>>> satellite in mdl_hypergraph_backbone(G).backbone
False
>>> local = local_mdl_hypergraph_backbone(G)  # majority rule
>>> satellite in local.backbone
True
>>> len(local.backbone)
3
>>> local.local_backbones[6] == [satellite]
True

Computational complexity estimate is O(sum_i k \|G_i\|^2 log \|G_i\|) time and O(sum_i \|G_i\|^2) space.

nx_backbone.hypergraph_compression_ratio(hyperedges, weights=None, gamma=1.0, prior='poisson')[source]#

Inverse compression ratio eta of the MDL backbone (Eq. (8)).

A convenience wrapper returning only HypergraphBackbone.compression_ratio from mdl_hypergraph_backbone(). eta lies in [0, 1]; values near 0 indicate a highly redundant (compressible) hypergraph, while eta = 1 indicates no compressible structure.

Parameters:

hyperedgesiterable of iterables: The hypergraph.
weightsiterable of numbers or None, optional (default=None): Optional per-hyperedge weights.
gammafloat, optional (default=1.0): Weight/topology trade-off (see mdl_hypergraph_backbone()).
prior{“poisson”, “geometric”}, optional (default=”poisson”): Weight prior family.

Returns:

etafloat: Inverse compression ratio in [0, 1].

Raises:

ValueError: For invalid weights, gamma, or prior (see mdl_hypergraph_backbone()).

See also

mdl_hypergraph_backbone: The full backbone and diagnostics.

Examples

>>> from nx_backbone import hypergraph_compression_ratio
>>> eta = hypergraph_compression_ratio([(1, 2, 3, 4), (1, 2, 3), (2, 3, 4)])
>>> 0.0 <= eta <= 1.0
True

Computational complexity estimate is O(sum_i \|G_i\|^2 + P log P) time and O(m + P) space.

nx_backbone.intersection_graph(hyperedges, s=1, weight='overlap')[source]#

Build the intersection graph (or s-line graph) of a hypergraph.

Each hyperedge becomes a node (labeled by its integer index after deduplication); two hyperedges are linked when they share at least s nodes. With s=1 this is the intersection graph over which MDL parent–child relationships are formed (Kirkley et al. 2026, Appendix D); with s > 1 it is the s-line graph, the basis of s-connectivity in higher-order networks.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Each hyperedge is an iterable of node labels.
sint, optional (default=1): Minimum shared-node count |e_i ∩ e_j| for two hyperedges to be linked. Must be >= 1.
weightstring, optional (default=”overlap”): Edge attribute name used to store the overlap size |e_i ∩ e_j|.

Returns:

Inetworkx.Graph: Graph on hyperedge indices. Each node has a "members" attribute (the hyperedge as a frozenset); each edge stores the overlap size under weight.

Raises:

ValueError: If s is less than 1.

See also

s_components: Connected components of the s-line graph.
hypergraph_to_bipartite: Node–hyperedge incidence graph.

Examples

>>> from nx_backbone import intersection_graph
>>> I = intersection_graph([(1, 2, 3), (2, 3, 4), (5, 6)])
>>> I.number_of_nodes()
3
>>> I[0][1]["overlap"]
2
>>> intersection_graph([(1, 2, 3), (2, 3, 4), (5, 6)], s=3).number_of_edges()
0

Computational complexity estimate is O(sum_i \|G_i\|^2) time and O(m + P) space.

class nx_backbone.HypergraphBackbone(backbone=<factory>, assignment=<factory>, n_nodes=0, n_orders=0, weighted=False, gamma=1.0, prior='poisson', description_length=0.0, baseline_description_length=0.0, compression_ratio=1.0, n_hyperedges=None, aggregation=None, local_backbones=<factory>, local_description_lengths=<factory>)[source]#

Bases: object

Result of mdl_hypergraph_backbone() or its local variant.

Attributes:

backbonelist of frozenset: The retained (“parent”) hyperedges forming the structural backbone.
assignmentdict: Mapping from each parent hyperedge to the list of child hyperedges it encodes (its star in the intersection graph). Parents with no children are absent from this mapping. Empty for a local backbone, which has no single global star partition (see local_backbones).
n_nodesint: Number of distinct nodes in the input hypergraph.
n_ordersint: Number of distinct hyperedge sizes (orders) in the input.
weightedbool: Whether edge weights influenced the backbone.
gammafloat: Weight/topology trade-off used (only meaningful when weighted).
priorstr: Weight prior used ("poisson" or "geometric").
description_lengthfloat: Description length L(G, B*) of the input given the backbone (bits).
baseline_description_lengthfloat: Description length L(G, G) with no backbone (bits).
compression_ratiofloat: Inverse compression ratio eta = L(G, B*) / L(G, G) in [0, 1]. Smaller means more redundant structure was removed. For a local backbone this is eta^(local) (Eq. (E4)).
n_hyperedgesint or None: Number of distinct (deduplicated, non-empty) input hyperedges, or None if unknown (then derived from backbone and assignment).
aggregationstr or None: For a local backbone, the rule used to combine the neighborhood backbones ("union", "majority" or "all"); None for the global backbone.
local_backbonesdict: For a local backbone, a mapping from each node i to its neighborhood backbone B_i* (a list of frozenset), the MDL optimum of the hyperedges containing i (Eq. (E1)). Empty otherwise.
local_description_lengthsdict: For a local backbone, a mapping from each node i to the neighborhood optimum L(G_i, B_i*) in bits. Empty otherwise.

Structural methods

Purely structural hypergraph backbones and utilities with no dyadic analog. These return plain hyperedge collections rather than a HypergraphBackbone.

nx_backbone.maximal_hyperedges(hyperedges)[source]#

Inclusion (toplex) reduction: keep only the maximal hyperedges.

Removes every hyperedge that is a strict subset of another hyperedge, retaining the toplexes – hyperedges not contained in any other. This is the simplest structural hypergraph backbone, pruning nested redundancy purely by set inclusion (cf. HyperNetX’s toplexes). For a richer, information-theoretic treatment of nested and overlapping redundancy, see mdl_hypergraph_backbone().

Parameters:

hyperedgesiterable of iterables: The hypergraph. Duplicate hyperedges are merged.

Returns:

maximallist of frozenset: The maximal hyperedges, ordered by decreasing size (ties broken by sorted node labels; labels of mixed, unorderable types are compared by repr).

See also

mdl_hypergraph_backbone: Information-theoretic pruning of nested and overlapping redundancy.
order_filter: Keep hyperedges by size.

Examples

>>> from nx_backbone import maximal_hyperedges
>>> sorted(map(sorted, maximal_hyperedges([(1, 2, 3), (1, 2), (2, 3), (4, 5)])))
[[1, 2, 3], [4, 5]]

Computational complexity estimate is O(m^2 * k) time and O(m) space.

nx_backbone.order_filter(hyperedges, min_order=None, max_order=None, orders=None)[source]#

Keep hyperedges whose order (size) falls in a range or set.

Order-resolved filtering has no analog in dyadic graphs, where every edge has order 2; in a hypergraph it selects interactions at chosen scales.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Duplicate hyperedges are merged.
min_orderint or None, optional (default=None): Keep hyperedges with size >= min_order.
max_orderint or None, optional (default=None): Keep hyperedges with size <= max_order.
ordersiterable of int or None, optional (default=None): If given, keep only hyperedges whose size is in this set (applied in addition to min_order/max_order).

Returns:

selectedlist of frozenset: The retained hyperedges, in first-occurrence order.

Raises:

ValueError: If min_order and max_order are both given and min_order > max_order.

See also

maximal_hyperedges: Structural (set-inclusion) pruning.
s_components: Group hyperedges by s-connectivity.

Examples

>>> from nx_backbone import order_filter
>>> sorted(map(sorted, order_filter([(1, 2), (1, 2, 3), (1, 2, 3, 4)], min_order=3)))
[[1, 2, 3], [1, 2, 3, 4]]

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

nx_backbone.s_components(hyperedges, s=1)[source]#

Group hyperedges into s-connected components.

Two hyperedges are s-adjacent when they share at least s nodes; an s-component is a connected component of the resulting s-line graph (intersection_graph() with the same s). s-connectivity is a higher-order notion with no dyadic counterpart and underlies s-centrality and s-distance analyses of hypergraphs.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Duplicate hyperedges are merged.
sint, optional (default=1): Minimum shared-node count for s-adjacency. Must be >= 1.

Returns:

componentslist of list of frozenset: Each inner list is the hyperedges of one s-connected component, ordered by decreasing component size (ties broken by sorted node labels; labels of mixed, unorderable types are compared by repr).

Raises:

ValueError: If s is less than 1.

See also

intersection_graph: The s-line graph whose components are returned.
maximal_hyperedges: Structural (set-inclusion) pruning.

Examples

>>> from nx_backbone import s_components
>>> comps = s_components([(1, 2, 3), (2, 3, 4), (5, 6, 7)], s=2)
>>> [len(c) for c in comps]
[2, 1]

Computational complexity estimate is O(sum_i \|G_i\|^2) time and O(m + P) space.

Statistical methods

Hypothesis-testing hypergraph backbones that validate hyperedges/groups recurring more than expected under a null model (Musciotto, Battiston & Mantegna, 2021). These require scipy and return a ValidatedHypergraph. The short names svh and svc are aliases for the two functions.

nx_backbone.statistically_validated_hypergraph(hyperedges, weights=None, max_order=None, alpha=0.01)[source]#

Extract the Statistically Validated Hypergraph (SVH).

Keeps the observed hyperedges that recur (co-occur) significantly more often than expected under a null model preserving node activity, following Musciotto, Battiston & Mantegna [1] (the method implemented as get_svh in Hypergraphx). Each hyperedge of order k is tested independently per order: with N order-k instances and node activities d_i (number of order-k instances containing node i), the probability of seeing a group co-occur at least n times is P(X >= n) for X ~ Binomial(N, prod_i d_i / N). P-values are validated with a Benjamini-Hochberg FDR at level alpha (corrected for the number of possible order-k hyperedges).

Unlike mdl_hypergraph_backbone() (an information-theoretic, parameter- free method), this is a statistical hypothesis test requiring a significance level, and is most informative for weighted hypergraphs whose weights are integer interaction multiplicities.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Duplicate hyperedges are merged (multiplicities summed).
weightsiterable of int or None, optional (default=None): Per-hyperedge integer multiplicities (interaction counts). None treats every hyperedge as occurring once.
max_orderint or None, optional (default=None): Only test hyperedges up to this order (size). None tests all orders.
alphafloat, optional (default=0.01): FDR significance level, in (0, 1].

Returns:

resultValidatedHypergraph: The validated hyperedges plus per-hyperedge p-values and counts.

Raises:

ValueError: If alpha is not in (0, 1], or weights has the wrong length or contains a value that is not an integer >= 1.

See also

statistically_validated_cores: Validates sub-groups (cores) as well.
mdl_hypergraph_backbone: Parameter-free information-theoretic backbone.

References

[1]

Musciotto, F., Battiston, F., & Mantegna, R. N. (2021). Detecting informative higher-order interactions in statistically validated hypergraphs. Communications Physics, 4, 218.

Examples

>>> from nx_backbone import statistically_validated_hypergraph
>>> edges = [(1, 2), (1, 2), (1, 2), (1, 3), (2, 4), (5, 6)]
>>> result = statistically_validated_hypergraph(edges)
>>> isinstance(result.validated, list)
True

Computational complexity estimate is O(sum_e \|e\| + m log m) time and O(m + n) space.

nx_backbone.statistically_validated_cores(hyperedges, weights=None, min_order=2, max_order=None, alpha=0.01, max_groups=1000000)[source]#

Extract the Statistically Validated Cores (SVC).

A complement to statistically_validated_hypergraph() that validates significant groups (cores) of nodes, including sub-groups that are not themselves present as a single hyperedge (the get_svc method of Hypergraphx, built on [1]). Orders are processed from high to low; once a core is validated, its sub-combinations are not re-tested at lower orders, so significance is attributed to the largest validated group. The co-occurrence of a group is the number of hyperedge instances (of any order) containing it, tested against Binomial(N, prod_i d_i / N) with global node activities, and validated with the same Benjamini-Hochberg FDR as SVH.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Duplicate hyperedges are merged (multiplicities summed).
weightsiterable of int or None, optional (default=None): Per-hyperedge integer multiplicities. None treats each as occurring once.
min_orderint, optional (default=2): Smallest group size to test (>= 1).
max_orderint or None, optional (default=None): Largest group size to test. None uses the largest hyperedge size. Every sub-group of every hyperedge up to this size is enumerated – up to 2**k per hyperedge of size k – so set it when the hypergraph contains large hyperedges.
alphafloat, optional (default=0.01): FDR significance level, in (0, 1].
max_groupsint or None, optional (default=1_000_000): Safety guard: if the number of candidate sub-groups to enumerate (summed over the distinct hyperedges, for orders min_order..max_order) exceeds this, a ValueError is raised before any work is done instead of running for an impractically long time. None disables the guard.

Returns:

resultValidatedHypergraph: The validated cores plus per-group p-values and co-occurrence counts.

Raises:

ValueError: If alpha is not in (0, 1], min_order is less than 1, weights is invalid, or the enumeration would exceed max_groups (lower max_order, or raise / disable max_groups).

See also

statistically_validated_hypergraph: Validates only observed hyperedges.
maximal_hyperedges: Purely structural pruning of nested hyperedges.

References

[1]

Musciotto, F., Battiston, F., & Mantegna, R. N. (2021). Detecting informative higher-order interactions in statistically validated hypergraphs. Communications Physics, 4, 218.

Examples

>>> from nx_backbone import statistically_validated_cores
>>> edges = [(1, 2, 3), (1, 2, 3), (1, 2, 3), (1, 4), (2, 5)]
>>> result = statistically_validated_cores(edges)
>>> result.method
'svc'
>>> # A single 24-node hyperedge has ~16.7 million sub-groups: bound the order.
>>> big = [tuple(range(24)), (0, 1), (0, 1), (0, 1)]
>>> len(statistically_validated_cores(big, max_order=3).pvalues)
2300

Computational complexity estimate is O(sum_e 2^\|e\|) time and O(G) space.

class nx_backbone.ValidatedHypergraph(validated=<factory>, pvalues=<factory>, counts=<factory>, alpha=0.01, method='svh', n_nodes=0, n_instances=0)[source]#

Bases: object

Result of statistically_validated_hypergraph() / cores.

Attributes:

validatedlist of frozenset: The statistically validated hyperedges (SVH) or cores (SVC) – the sub-hypergraph that survived FDR validation.
pvaluesdict: Mapping from each tested hyperedge/group to its p-value.
countsdict: Mapping from each tested hyperedge/group to its observed co-occurrence count (multiplicity for SVH; number of containing instances for SVC).
alphafloat: Significance level used for FDR validation.
methodstr: "svh" or "svc".
n_nodesint: Number of distinct nodes in the input hypergraph.
n_instancesint: Total number of hyperedge instances (sum of multiplicities).

Method gallery

mdl_hypergraph_backbone() on the Davis Southern Women hypergraph (each of the 14 events is a hyperedge on the women who attended it), global MDL, parameter-free.

Bipartite drawing of the Davis Southern Women hypergraph: 14 events (squares) linked to the 18 women who attended them (circles), with the hyperedges kept by mdl_hypergraph_backbone highlighted. Kept 4 of 14 hyperedges, covering 16 of 18 women. — Kept hyperedges in blue. Kept 4 of 14 hyperedges, covering 16 of 18 women.#

local_mdl_hypergraph_backbone() on the Davis Southern Women hypergraph (each of the 14 events is a hyperedge on the women who attended it), local MDL, defaults.

Interoperability and ingestion

Convert between the hyperedge-list representation and a NetworkX incidence bipartite graph (enabling the bipartite projection backbones), the HIF interchange format, and the xgi / HyperNetX / HypergraphX / HAT hypergraph classes. The third-party libraries are optional and imported lazily.

Hypergraph ingestion and interoperability adapters.

nx_backbone represents a hypergraph as a plain iterable of hyperedges (each an iterable of node labels), which every hypergraph backbone method in nx_backbone.hypergraph consumes. This module converts that representation to and from:

a NetworkX incidence bipartite graph, so bipartite projection backbones (sdsm(), fdsm(), …) can be applied to hypergraphs;
the HIF (Hypergraph Interchange Format) JSON standard;
the xgi, HyperNetX, HypergraphX, and Hypergraph Analysis Toolbox (HAT) hypergraph classes.

The third-party libraries are imported lazily; none is a required dependency. HIF is the recommended interchange path because all four libraries read and write it, so it needs only the standard library.

nx_backbone.hypergraph_to_bipartite(hyperedges, edge_prefix='he')[source]#

Convert a hypergraph to its incidence bipartite graph.

Nodes of the hypergraph form one partition (bipartite=0); hyperedges form the other (bipartite=1). The i-th (non-empty) hyperedge becomes the node (edge_prefix, i) – a tuple label, so it cannot be confused with a string node label such as "he0" – carrying a "members" attribute with the hyperedge as a frozenset. The result is exactly the input expected by the bipartite projection backbones, so a hypergraph can be backboned with, e.g., sdsm() or fdsm().

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped.
edge_prefixhashable, optional (default=”he”): First element of the (edge_prefix, i) hyperedge-node labels.

Returns:

Bnetworkx.Graph: The incidence bipartite graph.
nodeslist: The hypergraph’s nodes (the agent partition), suitable to pass as agent_nodes to the bipartite methods. Sorted in natural order when the labels are mutually comparable, otherwise by repr.

Raises:

ValueError: If a hyperedge label (edge_prefix, i) coincides with a hypergraph node label (choose a different edge_prefix).

See also

sdsm, fdsm: Bipartite projection backbones that consume the result.
intersection_graph: Hyperedge-level (line-graph) view of a hypergraph.

Examples

>>> import networkx as nx
>>> import nx_backbone as nb
>>> B, nodes = nb.hypergraph_to_bipartite([(1, 2, 3), (2, 3, 4), (5, 6)])
>>> nx.is_bipartite(B)
True
>>> nodes
[1, 2, 3, 4, 5, 6]
>>> sorted(B[("he", 0)])
[1, 2, 3]
>>> scored = nb.sdsm(B, agent_nodes=nodes)

nx_backbone.read_hif(source, return_weights=False)[source]#

Read a hypergraph from the HIF (Hypergraph Interchange Format) standard.

JSON arrays used as node or edge identifiers are converted to tuples so they are hashable (this restores tuple node labels written by write_hif()).

Parameters:

sourcedict, str, path, or file-like: A parsed HIF dictionary, a path to a HIF JSON file, or an open file.
return_weightsbool, optional (default=False): If True, also return per-hyperedge weights, read from each edges record’s weight (or attrs["weight"]) and defaulting to 1.

Returns:

hyperedgeslist of frozenset: The hyperedges, in order of first appearance among the incidences.
weightslist of numbers: Returned only when return_weights is True.

Raises:

TypeError: If source is not a dict, path, or file-like object.
networkx.NetworkXNotImplemented: If the HIF network-type is "directed" (directed hyperedges would otherwise silently lose their head/tail orientation).
ValueError: If the HIF network-type is not a recognized value.

See also

write_hif: The inverse operation.

Examples

>>> import nx_backbone as nb
>>> hif = nb.write_hif([(1, 2, 3), (3, 4)], weights=[2, 1])
>>> edges, weights = nb.read_hif(hif, return_weights=True)
>>> [sorted(e) for e in edges], weights
([[1, 2, 3], [3, 4]], [2, 1])

nx_backbone.write_hif(hyperedges, target=None, weights=None, network_type='undirected')[source]#

Serialise a hypergraph to the HIF (Hypergraph Interchange Format) standard.

HIF is a JSON format shared by xgi, HyperNetX, HypergraphX, and HAT, making it the most portable interchange path. Numpy scalar node labels and weights are converted to builtin Python numbers so the result is JSON-serialisable. Tuple node labels are written as JSON arrays and restored as tuples by read_hif().

The output always has nodes and edges lists, which the HAT and HypergraphX readers require. Hyperedge weights go in the edge records’ weight field, as the HIF schema specifies. HyperNetX and HAT read them; xgi’s reader keeps only attrs and HypergraphX’s ignores weights, so for those two use to_xgi(*read_hif(path, return_weights=True)) (or to_hypergraphx()) instead of the library’s own reader.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped.
targetstr, path, file-like, or None, optional (default=None): Where to write. If None, the HIF dictionary is returned instead of being written.
weightsiterable of numbers or None, optional (default=None): Optional per-hyperedge weights, written to the HIF edges list.
network_type{“undirected”, “asc”}, optional (default=”undirected”): Value for the HIF network-type field.

Returns:

resultdict or target: The HIF dictionary if target is None; otherwise target.

Raises:

ValueError: If weights does not match hyperedges in length, or network_type is not a valid HIF network type.
networkx.NetworkXNotImplemented: If network_type is "directed" (hyperedges here are undirected).

See also

read_hif: The inverse operation.

Examples

>>> import nx_backbone as nb
>>> hif = nb.write_hif([(1, 2, 3), (3, 4)], weights=[2, 1])
>>> hif["network-type"]
'undirected'
>>> len(hif["incidences"])
5
>>> hif["edges"]
[{'edge': 0, 'weight': 2}, {'edge': 1, 'weight': 1}]
>>> hif["nodes"][:2]
[{'node': 1}, {'node': 2}]

nx_backbone.from_xgi(H, return_weights=False)[source]#

Convert an xgi.Hypergraph to a list of frozenset hyperedges.

Parameters:

Hxgi.Hypergraph: The xgi hypergraph (read via H.edges.members(dtype=dict)).
return_weightsbool, optional (default=False): If True, also return each edge’s "weight" attribute (default 1).

Returns:

hyperedgeslist of frozenset: One frozenset per xgi hyperedge, in xgi’s edge order. Multi-edges are kept; edge IDs are discarded.
weightslist of numbers: Returned only when return_weights is True.

See also

to_xgi: The inverse conversion.
read_hif: Library-independent interchange via HIF.

Examples

>>> import xgi
>>> import nx_backbone as nb
>>> nb.from_xgi(xgi.Hypergraph([[1, 2, 3], [3, 4]]))
[frozenset({1, 2, 3}), frozenset({3, 4})]

nx_backbone.to_xgi(hyperedges, weights=None)[source]#

Convert hyperedges to an xgi.Hypergraph.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped; the remaining edges get the IDs 0, 1, 2, .... Repeated hyperedges become xgi multi-edges.
weightsiterable of numbers or None, optional (default=None): Per-hyperedge weights (aligned with hyperedges), stored as the "weight" edge attribute.

Returns:

Hxgi.Hypergraph: The equivalent xgi hypergraph.

Raises:

ImportError: If xgi is not installed.
ValueError: If weights does not match hyperedges in length.

See also

from_xgi: The inverse conversion.
write_hif: Library-independent interchange via HIF.

Examples

>>> import nx_backbone as nb
>>> H = nb.to_xgi([(1, 2, 3), (3, 4)], weights=[2.0, 1.0])
>>> H.num_edges
2

nx_backbone.from_hypernetx(H, return_weights=False)[source]#

Convert a hypernetx.Hypergraph to a list of frozenset hyperedges.

Parameters:

Hhypernetx.Hypergraph: The HyperNetX hypergraph (read via H.incidence_dict).
return_weightsbool, optional (default=False): If True, also return each edge’s HyperNetX weight property (HyperNetX defaults it to 1 and stores it as a float).

Returns:

hyperedgeslist of frozenset: One frozenset per HyperNetX edge, in incidence_dict order (edge names are discarded).
weightslist of numbers: Returned only when return_weights is True.

See also

to_hypernetx: The inverse conversion.
read_hif: Library-independent interchange via HIF.

Examples

>>> import hypernetx as hnx
>>> import nx_backbone as nb
>>> nb.from_hypernetx(hnx.Hypergraph({"a": [1, 2], "b": [2, 3]}))
[frozenset({1, 2}), frozenset({2, 3})]

nx_backbone.to_hypernetx(hyperedges, weights=None)[source]#

Convert hyperedges to a hypernetx.Hypergraph.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped; the remaining edges are named 0, 1, 2, ....
weightsiterable of numbers or None, optional (default=None): Per-hyperedge weights (aligned with hyperedges), stored as the HyperNetX edge weight property.

Returns:

Hhypernetx.Hypergraph: The equivalent HyperNetX hypergraph.

Raises:

ImportError: If hypernetx is not installed.
ValueError: If weights does not match hyperedges in length.

See also

from_hypernetx: The inverse conversion.
write_hif: Library-independent interchange via HIF.

Examples

>>> import nx_backbone as nb
>>> H = nb.to_hypernetx([(1, 2, 3), (3, 4)])
>>> sorted(H.incidence_dict)
[0, 1]

nx_backbone.from_hypergraphx(H, return_weights=False)[source]#

Convert a hypergraphx.Hypergraph to a list of frozenset hyperedges.

Parameters:

Hhypergraphx.Hypergraph: The HypergraphX hypergraph (read via H.get_edges()).
return_weightsbool, optional (default=False): If True, also return each edge’s weight (H.get_weight; 1 in an unweighted HypergraphX hypergraph).

Returns:

hyperedgeslist of frozenset: One frozenset per HypergraphX hyperedge.
weightslist of numbers: Returned only when return_weights is True.

See also

to_hypergraphx: The inverse conversion.
read_hif: Library-independent interchange via HIF.

Examples

>>> import hypergraphx as hgx
>>> import nx_backbone as nb
>>> nb.from_hypergraphx(hgx.Hypergraph(edge_list=[(1, 2), (2, 3, 4)]))
[frozenset({1, 2}), frozenset({2, 3, 4})]

nx_backbone.to_hypergraphx(hyperedges, weights=None)[source]#

Convert hyperedges to a hypergraphx.Hypergraph.

HypergraphX has no multi-edges, so repeated hyperedges are merged into one edge whose weight is the sum of theirs (each counts 1 when weights is None). The result is weighted when weights is given or a hyperedge repeats, and unweighted otherwise.

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped. HypergraphX sorts the nodes of each hyperedge, so node labels must be mutually comparable.
weightsiterable of numbers or None, optional (default=None): Per-hyperedge weights (aligned with hyperedges).

Returns:

Hhypergraphx.Hypergraph: The equivalent HypergraphX hypergraph (built from an edge_list of tuples).

Raises:

ImportError: If hypergraphx is not installed.
ValueError: If weights does not match hyperedges in length.
TypeError: If the node labels of a hyperedge cannot be sorted (for example, a mix of int and str).

See also

from_hypergraphx: The inverse conversion.
write_hif: Library-independent interchange via HIF.

Examples

>>> import nx_backbone as nb
>>> H = nb.to_hypergraphx([(1, 2, 3), (3, 4), (3, 4)])
>>> nb.from_hypergraphx(H, return_weights=True)
([frozenset({1, 2, 3}), frozenset({3, 4})], [1, 2])

nx_backbone.from_hat(H, return_weights=False)[source]#

Convert a HAT Hypergraph to a list of frozenset hyperedges.

HAT stores nodes by position (row of the incidence matrix). Node labels are read from the "Names" column of H.nodes when it exists (HAT fills it when built from labeled edges, and to_hat() sets it), else from its "Nodes" column (row indices, or the HIF node IDs for a hypergraph from HAT.Hypergraph.from_hif), else the row indices.

Parameters:

HHAT.Hypergraph: The HAT hypergraph. Its node-by-edge incidence matrix is read from the IM, incidence_matrix, or incidenceMatrix attribute (dense or scipy sparse; a method is called).
return_weightsbool, optional (default=False): If True, also return the "weight" column of H.edges (default 1).

Returns:

hyperedgeslist of frozenset: One frozenset per non-empty incidence-matrix column.
weightslist of numbers: Returned only when return_weights is True.

Raises:

ImportError: If numpy is not installed.
AttributeError: If no incidence matrix can be found on H.

See also

to_hat: The inverse conversion.
read_hif: Library-independent interchange via HIF.

Examples

>>> import nx_backbone as nb
>>> H = nb.to_hat([("a", "b"), ("b", "c", "d")])
>>> nb.from_hat(H)
[frozenset({'a', 'b'}), frozenset({'b', 'c', 'd'})]

nx_backbone.to_hat(hyperedges, weights=None)[source]#

Convert hyperedges to a HAT Hypergraph via an incidence matrix.

HAT is positional: node i is row i of the incidence matrix. Rows follow sorted label order (natural order when the labels are mutually comparable, otherwise by repr), and the labels are kept in the "Names" column of H.nodes, where from_hat() finds them. Repeated hyperedges are kept (HAT’s own duplicate removal is turned off).

Parameters:

hyperedgesiterable of iterables: The hypergraph. Empty hyperedges are skipped.
weightsiterable of numbers or None, optional (default=None): Per-hyperedge weights (aligned with hyperedges), stored in the "weight" column of H.edges (HAT’s edge_weights).

Returns:

HHAT.Hypergraph: A HAT hypergraph built from the nodes x hyperedges 0/1 incidence matrix (HAT.Hypergraph(incidence_matrix=..., compress=False)).

Raises:

ImportError: If numpy or HAT (pip install HypergraphAnalysisToolbox) is not installed.
ValueError: If weights does not match hyperedges in length.

See also

from_hat: The inverse conversion.
write_hif: Library-independent interchange via HIF.

Examples

>>> import nx_backbone as nb
>>> H = nb.to_hat([("a", "b"), ("b", "c", "d")], weights=[2, 1])
>>> list(H.edge_weights)
[2, 1]