Source code for xgi.convert.encapsulation_dag

import networkx as nx

from ..exception import XGIError

__all__ = ["to_encapsulation_dag", "empirical_subsets_filter"]


[docs]def to_encapsulation_dag(H, subset_types="all"): """The encapsulation DAG (Directed Acyclic Graph) of the hypergraph H. An encapsulation DAG is a directed line graph where the nodes are hyperedges in H and a directed edge exists from a larger hyperedge to a smaller hyperedge if the smaller is a subset of the larger. Parameters ---------- H : Hypergraph The hypergraph of interest subset_types : str, optional Type of relations to include. Options are: * "all" : all subset relationships * "immediate" : only subset relationships between hyperedges of adjacent sizes (i.e., edges from k to k-1) * "empirical" : A relaxation of the "immediate" option where only subset relationships between hyperedges of size k and subsets of maximum size k'<k existing in the hypergraph are included. For example, a hyperedge of size 5 may have no immediate encapsulation relationships with hyperedges of size 4, but may encapsulate hyperedegs of size 3, which will be included if using this setting (whereas relationships with subsets of size 2 would not be included). Returns ------- LG : networkx.DiGraph The line graph associated to the Hypergraph Examples -------- >>> import xgi >>> from xgi.convert import to_encapsulation_dag, empirical_subsets_filter >>> H = xgi.Hypergraph([["a","b","c"], ["b","c","f"], ["a","b"], ["c", "e"], ["a"], ["f"]]) >>> dag = to_encapsulation_dag(H) >>> dag.edges() OutEdgeView([(0, 2), (0, 4), (2, 4), (1, 5)]) >>> dag = to_encapsulation_dag(H, subset_types="immediate") >>> dag.edges() OutEdgeView([(0, 2), (2, 4)]) >>> dag = to_encapsulation_dag(H, subset_types="empirical") >>> dag.edges() OutEdgeView([(0, 2), (2, 4), (1, 5)]) References ---------- "Encapsulation Structure and Dynamics in Hypergraphs", by Timothy LaRock & Renaud Lambiotte. https://arxiv.org/abs/2307.04613 """ if not (subset_types in ["all", "immediate", "empirical"]): raise XGIError( f"{subset_types} not a valid subset_types option. Choices are " "'all', 'immediate', and 'empirical'." ) # Construct the dag dag = nx.DiGraph() # Loop over hyperedges for he_idx in H.edges: # Add the hyperedge as a node dag.add_node(he_idx) # Get the hyperedge as a set he = H.edges.members(he_idx) # Get candidate encapsulation hyperedges candidates = _get_candidates(subset_types, H, he) # for each candidate candidates_checked = set() for cand_idx in candidates: if cand_idx in candidates_checked: continue cand = H.edges.members(cand_idx) if len(he) > len(cand): if _encapsulated(he, cand): dag.add_edge(he_idx, cand_idx) elif len(cand) > len(he): if _encapsulated(cand, he): dag.add_edge(cand_idx, he_idx) # If empirically closest subsets, filter out all edges except those # between k and maximum existing k'<k if subset_types == "empirical": empirical_subsets_filter(H, dag) return dag
def _encapsulated(larger, smaller): """Test if a larger hyperedge encapsulates a smaller hyperedge. Parameters ---------- larger : Set larger hyperedge smaller : Set smaller hyperedge Returns ------- _ : Bool True if the size of the intersection between larger and smaller is the same as the size of smaller. """ return len(set(larger).intersection(set(smaller))) == len(smaller) def _get_candidates(subset_types, H, he): """Get the candidate hyperedges for encapsulation by he based on the subset type. Parameters ---------- subset_types : str Type of subset relationships H : Hypergraph The hypergraph he : Set The hyperedge Returns ------- candidates : Set A set of hyperedge IDs to check for encapsulation by hyperedge he """ candidates = set() for node in he: for cand_idx in H.nodes.memberships(node): if cand_idx not in candidates: cand = H.edges.members(cand_idx) if _check_candidate(subset_types, he, cand): candidates.add(cand_idx) return candidates def _check_candidate(subset_types, he, cand): """Check whether a hyperedge cand is a candidate to be encapsulated by hyperedge he based on subset_types. Parameters ---------- subset_types : str Type of subset relationships he : Set The hyperedge cand : Set The candidate Returns ------- is_candidate : bool True if cand is a valid candidate to be encapsulated by he, False otherwise. """ is_candidate = False if subset_types in ["all", "empirical"]: if len(he) != len(cand): is_candidate = True elif subset_types == "immediate": if len(he) == len(cand) - 1 or len(he) - 1 == len(cand): is_candidate = True return is_candidate
[docs]def empirical_subsets_filter(H, dag): """ Filters encapsulation DAG of H in place to only include edges between hyperedges of size k and the maximum existing k'. Parameters ---------- H : Hypergraph The hypergraph of interest dag : nx.DiGraph The encapsulation dag of H constructed with to_encapsulation_dag(H, subset_types="all") Returns ------- dag : networkx.DiGraph The filtered line graph (also modified in place) References ---------- "Encapsulation Structure and Dynamics in Hypergraphs", by Timothy LaRock & Renaud Lambiotte. https://arxiv.org/abs/2307.04613 """ # Loop over all edges for edge_idx in dag: preds = list(dag.predecessors(edge_idx)) if len(preds) > 0: # Get the minimum superface size min_sup_size = min([len(H.edges.members(cand_idx)) for cand_idx in preds]) # Keep only the superfaces with that size to_remove = [] for cand_idx in preds: if len(H.edges.members(cand_idx)) != min_sup_size: dag.remove_edge(cand_idx, edge_idx) # Repeat for subsets outs = list(dag.successors(edge_idx)) if len(outs) > 0: max_sub_size = max([len(H.edges.members(sub_idx)) for sub_idx in outs]) for cand_idx in outs: if len(H.edges.members(cand_idx)) != max_sub_size: dag.remove_edge(edge_idx, cand_idx) return dag