Skip to content

Improve the to_encapsulation_dag function #715

Description

@nwlandry

I propose two improvements:

  1. Add an option to make nodes in the DAG the hyperedge IDs or alternatively, frozensets of the edges themselves.
  2. Make the computation faster. Below is an example which seems to be roughly 3x faster than the current version:
def to_encapsulation_dag_fast(H, subset_types="all", nodes_as_sets=False):
    """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

    """
    edge_dict = H.edges.members(dtype=dict)
    # Construct the dag
    dag = nx.MultiDiGraph()
    # Loop over hyperedges

    it = 0
    for idx1 in edge_dict:
        # Add the hyperedge as a node
        # Get the hyperedge as a set
        if nodes_as_sets:
            e1 = frozenset(edge_dict[idx1])
            dag.add_node(e1)
        else:
            dag.add_node(idx1)
        # Get candidate encapsulation hyperedges
        s_neighbors = H.edges.neighbors(idx1, s=len(e1))
        if nodes_as_sets:
            dag.add_edges_from([[frozenset(edge_dict[idx2]), e1] for idx2 in s_neighbors])
        else:
            dag.add_edges_from([[idx2, idx1] for idx2 in s_neighbors])
        it += 1
        if it % 1000 == 0:
            print(f"Processed {it} hyperedges.")
    return dag

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    improveMake an existing feature better

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions