Glossary of HNX terms

Note: For all definitions below, assume \(H = (V, E, \mathcal{I})\) is a hypergraph.

degree

Given a hypergraph \(H = (V, E, \mathcal{I})\), the degree of a node in \(V\) is the number of edges in \(E\) to which the node is incident. See also: s-degree

dual

The dual of a hypergraph exchanges the roles of the edges and nodes in the hypergraph. For a hypergraph \(H = (V, E, \mathcal{I})\) the dual is \(H_D = (E, V, \mathcal{I}^T)\) where the ordered pairs in \(\mathcal{I}^T\) are the transposes of the ordered pairs in \(\mathcal{I}\). The incidence matrix of \(H_D\) is the transpose of the incidence matrix of \(H\).

edges

hyperedges

A set of objects distinguished by unique identifiers (uids). Each edge has metadata associated with it. Edges are assigned a weight either by default or specified by the user. Edges contain nodes. Nodes are elements of edges.

elements

The elements of an edge is the set of nodes incident to the edge in the Hypergraph.

hypergraph

A hypergraph is a tuple of three sets, \(H = (V, E, \mathcal{I})\).

\(V\), a set of nodes (aka hypernodes, vertices), distinguished by unique identifiers
\(E\) a set of edges (aka hyperedges), distinguished by unique identifiers
\(\mathcal{I}\), a set of incidences, which form a subset of \(E \times V\), distinguished by the pairing of unique identifiers of edges in \(E\) and nodes in \(V\)

HypergraphView

Class in hyp_view.py tying the properties of hypergraph objects held in the PropertyStore class, which holds metadata, with their ids held in the IncidenceStore class, which holds the Hypergraph relationships. The PropertyStores are unaware of the IncidenceStore and vice versa.

incidence matrix

A rectangular matrix constructed from a hypergraph, \(H = (V, E, \mathcal{I})\). The rows of the matrix are indexed by \(V\). The columns of the matrix are indexed by \(E\). An entry in the matrix at position \((v,e)\) for some \(v \in V\) and \(e \in E\) is nonzero if and only if \((e,v) \in I\). A weighted incidence matrix uses the incidence weight associated with \((e,v)\) for the nonzero entry. An unweighted incidence matrix has the integer \(1\) in all nonzero entries.

incidences

The ordered pairs in \(\mathcal{I} \subset E \times V\), which define the relationships in the hypergraph. The incidences \(\mathcal{I}\) of a hypergraph provide the minimal amount of data required to instantiate the hypergraph. The Edges \(E\) and Nodes \(V\) of a Hypergraph can be inferred from the pairs \((e,v)\) in the Incidences.

Each incidence uniquely identifies a single edge and node. Each incidence has metadata assigned to it. Incidences in a hypergraph are assigned a weight either by default or specified by a user. If \((e,v) \in \mathcal{I}\) then \(e\) contains \(v\), \(v\) is an element of \(e\), and \(v\) has membership in \(e\).

IncidenceStore

Class in incidence_store.py holding the set of ordered pairs of Edges and Nodes belonging to the hypergraph. The elements and memberships are inferred from the incidences held in the IncidenceStore.

memberships

The memberships of a node is the set of edges incident to the node in the Hypergraph.

multihypergraph

HNX hypergraphs may be multihypergraphs. A multihypergraph is a hypergraph that allows distinct edges to contain the same set of elements and distinct nodes to belong to the same set of edges (aka memberships). When collapsing a hypergraph, edges incident with the same set of nodes or nodes incident with the same set of edges are collapsed to single objects.

nodes

vertices

hypernodes

A set of objects distinguished by unique identifiers (uids). Each node has metadata associated with it. Nodes are assigned a weight either by default or specified by the user. Nodes belong to edges. Nodes have memberships in edges.

PropertyStore

Class in property_store.py. Each of the basic sets in a hypergraph, (Nodes, Edges, Incidences), have metadata stored in a PropertyStore. By storing the data and metadata in a single place, updates and references have a single source of truth.

s-adjacency matrix

For a positive integer s, a square matrix for a hypergraph, \(H = (V, E, \mathcal{I})\), indexed by \(V\) such that an entry \((v_1,v_2)\) is nonzero if only if \(v_1, v_2 \in V\) are s-adjacent. An s-adjacency matrix can be weighted or unweighted, in which case all entries are 0’s and 1’s.

s-adjacent

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, two nodes in \(V\) are s-adjacent if there are at least s edges in \(E\), which contain both of them.

s-auxiliary matrix

s-edge-auxiliary matrix

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, the submatrix of the s-adjacency matrix or the s-edge-adjacency matrix obtained by removing all 0-rows and 0-columns.

s-connected

s-node-connected

s-edge-connected

A hypergraph is s-connected if it has one s-connected component. Similarly for s-node-connected and s-edge-connected.

s-connected component

s-node-connected component

s-edge-connected component

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, an s-connected component is a subhypergraph induced by a subset of \(V\) with the property that there exists an s-walk between every pair of nodes in this subset. An s-connected component is the maximal such subset in the sense that it is not properly contained in any other subset satisfying this property.

An s-node-connected component is an s-connected component. An s-edge-connected component is an s-connected component of the dual of \(H\).

s-degree

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, the s-degree of a node, \(v \in V\) is the number of edges in \(E\) of size at least s to which \(v\) belongs. See also: degree

s-diameter

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, the s-diameter is the maximum s-distance over all pairs of nodes in \(V\).

s-distance

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, the s-distances between two nodes in \(V\) is the length of the shortest s-node-walk between them. If no s-node-walk between the pair of nodes exists, the s-distance between them is infinite.

s-edge

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, an s-edge is any edge \(e \in E\) of size at least s, where the size of \(e\) equals the number of nodes in \(V\) belonging to \(e\).

s-edge-adjacency matrix

An s-edge-adjacency matrix is the s-adjacency matrix for the dual of \(H\).

s-edge-adjacent

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, two edges in \(E\) are s-edge-adjacent if they there are at least s nodes in \(V\) belonging to both of them. Another way of saying this is two edges are s-edge-adjacent if they are s-adjacent in the dual of \(H\).

s-edge-distance

The s-edge-distance between two edges in \(E\) is the length of the shortest s-edge-walk between them. If no s-edge-walk between the pair of edges exists, then s-distance between them is infinite.

s-edge-walk

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, a sequence of edges in \(E\) such that each successive pair of edges are s-edge-adjacent. The length of the s-edge-walk is the number of adjacent pairs in the sequence.

s-linegraph

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, an s-linegraph \(G\) is a graph representing the node to node or edge to edge connections defined by the s-adjacency matrices.

The node s-linegraph, \(G_V\) is a graph on the set \(V\). Two nodes in \(V\) are incident in \(G_V\) if they are s-adjacent.

The edge s-linegraph, \(G_E\) is a graph on the set \(E\). Two edges in \(E\) are incident in \(G_E\) if they are s-edge-adjacent.

s-node-walk

For a hypergraph, \(H = (V, E, \mathcal{I})\), and positive integer s, a sequence of nodes in \(V\) such that each successive pair of nodes are s-adjacent. The length of the s-node-walk is the number of adjacent pairs in the sequence.

s-walk

Either an s-node-walk or an s-edge-walk. The length of the s-walk is the number of adjacent pairs in the sequence.

simple hypergraph

A hypergraph for which no edge is completely contained in another.

subhypergraph

A subhypergraph of a hypergraph, \(H = (V, E, \mathcal{I})\), is a hypergraph, \(H' = (V', E', \mathcal{I'})\) such that \((e',v') \in \mathcal{I'}\) if and only if \(e' \in E' \subset E\), \(v' \in V' \subset V\) and \((e,v) \in \mathcal{I}\).

toplex

A toplex in a hypergraph, \(H = (V, E, \mathcal{I})\), is an edge \(e \in E\) whose set of elements is not properly contained in any other edge in \(E\). That is, if \(f \in E\) and the elements of \(e\) are all elements of \(f\) then the elements of \(f\) are all elements of \(e\).