HAT Documentation

This page provides an overview of the Hypergraph class and its associated modules, which offer tools for analyzing, visualizing, and working with the structure and dynamics of hypergraphs.

Hypergraph Class

The Hypergraph class serves as the core data structure in HAT. It represents a hypergraph’s nodes, hyperedges, and related metadata. It also supports a variety of numerical representations, including tensors and incidence matrices.

Creating a Hypergraph object provides access to additional analysis and visualization functionality across the toolbox’s modules.

class HAT.hypergraph.Hypergraph(edge_list=None, adjacency_tensor=None, incidence_matrix=None, nodes=None, edges=None, uniform=None, order=None, directed=None, compress=True, verbose=False)[source]

Bases: object

Represents a hypergraph structure, enabling complex multi-way relationships between nodes.

This class implements a hypergraph where edges (or hyperedges) can connect multiple vertices. Internally, the hypergraph can be represented by an incidence matrix, an adjacency tensor, or an edge list, depending on the available inputs and the uniformity of the hypergraph.

Formally, a hypergraph \(H=(V,E)\) is defined by a set of vertices \(V\) and a set of edges \(E\), where each edge \(e \in E\) may contain any subset of vertices in \(V\). Unlike traditional graphs, hypergraph edges can connect more than two vertices, allowing for multi-way interactions. Uniform hypergraphs, where all edges have the same number of vertices, can be efficiently represented using tensors.

edge_list

Stores the list of edges if provided during initialization.

Type:

list of lists or None

adjacency_tensor

Stores the adjacency tensor if provided during initialization.

Type:

ndarray or None

incidence_matrix

Stores the incidence matrix if generated or provided during initialization.

Type:

ndarray or None

nodes

Array of nodes (vertices) in the hypergraph.

Type:

ndarray or None

edges

Array of edges (hyperedges) in the hypergraph.

Type:

ndarray or None

uniform

Indicates if the hypergraph is uniform.

Type:

bool

k

The degree of uniformity in terms of edge size, if applicable.

Type:

int

directed

Indicates if the hypergraph is directed.

Type:

bool, default=False

verbose

Additional warning messages display when true

Type:

bool, default=False

property nodes
property edges
property directed
property nnodes

Returns the number of nodes (vertices) in the hypergraph.

Returns:

Number of nodes in the hypergraph.

Return type:

int

property nedges

Returns the number of edges (hyperedges) in the hypergraph.

Returns:

Number of edges if available, otherwise False if edges are not defined.

Return type:

int or bool

property edge_weights
property node_weights
property uniform

Returns if the hypergraph was uniform.

property order
property incidence_matrix

Returns the incidence matrix of the hypergraph, constructing it if necessary.

property edge_list

Returns the edge list of the hypergraph, constructing it if necessary.

property adjacency_tensor

Returns the adjacency tensor of the hypergraph, constructing it if necessary.

property star_graph
property clique_graph
property connected_components
property laplacian_matrix
add_node(properties=None)[source]

Adds a new node to self._nodes. Properties is a dictionary specifying values for the columns in self._nodes. Missing properties are filled with None.

Parameters:

properties (dict, optional) – A dictionary containing column names as keys and their corresponding values. Defaults to None.

add_edge(nodes, properties=None)[source]
property dual

The dual hypergraph is constructed. Let \(H=(V,E)\) be a hypergraph. In the dual hypergraph each original edge \(e in E\) is represented as a vertex and each original vertex \(v in E\) is represented as an edge. Numerically, the transpose of the incidence matrix of a hypergraph is the incidence matrix of the dual hypergraph.

Returns:

Hypergraph object

Return type:

Hypergraph

References

  • Yang, Chaoqi, et al. “Hypergraph learning with line expansion.” arXiv preprint arXiv:2005.04843 (2020).

property hif
property hypernetx
classmethod from_hypernetx(HG_hnx)[source]
classmethod from_networkx(nxg)[source]
classmethod from_hif(hif)[source]
to_hif()[source]

Converts HAT.Hypergraph to Hypergraph Interchange Format (HIF)

property hypergraphx
HAT.hypergraph.convert_nodes_to_integers(edge_list)[source]

Tensor Representations

HAT.tensors.adjTensor(HG)[source]

This constructs the adjacency tensor for uniform hypergraphs.

Returns:

Adjacency Tensor

Return type:

ndarray

The adjacency tensor \(A\) of a \(k-`order hypergraph :math:`H\) is the multi-way, hypergraph analog of the pairwise, graph adjacency matrix. It is defined as a \(k-\) mode tensor ( \(k-\) dimensional matrix):

\[\begin{split}A \in \mathbf{R}^{ \overbrace{n \times \dots \times n}^{k \text{ times}}} \text{ where }{A}_{j_1\dots j_k} = \begin{cases} \frac{1}{(k-1)!} & \text{if }(j_1,\dots,j_k)\in {E}_h \\ 0 & \text{otherwise} \end{cases},\end{split}\]

as found in equation 8 of [1].

References

HAT.tensors.degreeTensor(HG)[source]

This constructs the degree tensor for uniform hypergraphs.

Returns:

Degree Tensor

Return type:

ndarray

The degree tensor \(D\) is the hypergraph analog of the degree matrix. For a \(k-\) order hypergraph \(H=(V,E)\) the degree tensor \(D\) is a diagonal supersymmetric tensor defined

\[D \in \mathbf{R}^{ \overbrace{n \times \dots \times n}^{k \text{ times}}} \text{ where }{D}_{i\dots i} = degree(v_i) \text{ for all } v_i\in V\]

References

HAT.tensors.laplacianTensor(HG)[source]

This constructs the Laplacian tensor for uniform hypergraphs.

Returns:

Laplcian Tensor

Return type:

ndarray

The Laplacian tensor is the tensor analog of the Laplacian matrix for graphs, and it is defined equivalently. For a hypergraph \(H=(V,E)\) with an adjacency tensor \(A\) and degree tensor \(D\), the Laplacian tensor is

\[L = D - A\]

References

HAT.tensors.tensorEntropy(HG)[source]

Computes hypergraph entropy based on the singular values of the Laplacian tensor.

Returns:

tensor entropy

Return type:

float

Uniform hypergraph entropy is defined as the entropy of the higher order singular values of the Laplacian matrix [1].

References

    1. Chen and I. Rajapakse, Tensor Entropy for Uniform Hypergraphs, IEEE TRANSACTIONS

    ON NETWORK SCIENCE AND ENGINEERING (2020) (Definition 7, Algorithm 1) https://arxiv.org/pdf/1912.09624.pdf

Laplacians

HAT.laplacian.laplacian_matrix(HG, laplacian_type='Bolla')[source]

This function returns a version of the higher order Laplacian matrix of the hypergraph.

Parameters:

type (str, optional) – Indicates which version of the Laplacin matrix to return. It defaults to Bolla [1], but Rodriguez [2,3] and Zhou [4] are valid arguments as well.

Returns:

Laplacian matrix

Return type:

ndarray

Several version of the hypergraph Laplacian are defined in [1-4]. These aim to capture the higher order structure as a matrix. This function serves as a wrapper to call functions that generate different specific Laplacians (See bolla_laplacian(), rodriguez_laplacian(), and zhou_laplacian()).

References

HAT.laplacian.bolla_laplacian(HG)[source]

This function constructs the hypergraph Laplacian according to [1].

Returns:

Bolla Laplacian matrix

Return type:

ndarray

References

HAT.laplacian.rodriguez_laplacian(HG)[source]

This function constructs the hypergraph Laplacian according to [1, 2].

Returns:

Rodriguez Laplacian matrix

Return type:

ndarray

References

HAT.laplacian.zhou_laplacian(HG)[source]

This function constructs the hypergraph Laplacian according to [1].

Returns:

Zhou Laplacian matrix

Return type:

ndarray

References

Graph Interface

HAT.graph.clique_graph(HG)[source]

The clique expansion graph is constructed.

Returns:

Clique expanded graph

Return type:

networkx.graph

The clique expansion algorithm constructs a graph on the same set of vertices as the hypergraph by defining an edge set where every pair of vertices contained within the same edge in the hypergraph have an edge between them in the graph. Given a hypergraph \(H=(V,E_h)\), then the corresponding clique graph is \(C=(V,E_c)\) where \(E_c\) is defined

\[E_c = \{(v_i, v_j) |\ \exists\ e\in E_h \text{ where } v_i, v_j\in e\}.\]

This is called clique expansion because the vertices contained in each \(h\in E_h\) forms a clique in \(C\). While the map from \(H\) to \(C\) is well-defined, the transformation to a clique graph is a lossy process, so the hypergraph structure of \(H\) cannot be uniquely recovered from the clique graph \(C\) alone [1].

References

  • Amit Surana, Can Chen, and Indika Rajapakse. Hypergraph similarity measures. IEEE Transactions on Network Science and Engineering, pages 1-16, 2022.

  • Yang, Chaoqi, et al. “Hypergraph learning with line expansion.” arXiv preprint arXiv:2005.04843 (2020).

HAT.graph.lineGraph(HG)[source]

The line graph, which is the clique expansion of the dual graph, is constructed.

Returns:

Line graph

Return type:

networkx.graph

References

  • Yang, Chaoqi, et al. “Hypergraph learning with line expansion.” arXiv preprint arXiv:2005.04843 (2020).

HAT.graph.star_graph(HG)[source]

The star graph representation is constructed.

Returns:

Star graph

Return type:

networkx.graph

The star expansion of \({H}=({V},{E}_h)\) constructs a bipartite graph \({S}=\{{V}_s,{E}_s\}\) by introducing a new set of vertices \({V}_s={V}\cup {E}_h\) where some vertices in the star graph represent hyperedges of the original hypergraph. There exists an edge between each vertex \(v,e\in {V}_s\) when \(v\in {V}\), \(e\in {E}_h,\) and \(v\in e\). Each hyperedge in \({E}_h\) induces a star in \(S\). This is a lossless process, so the hypergraph structure of \(H\) is well-defined] given a star graph \(S\).

References

  • Yang, Chaoqi, et al. “Hypergraph learning with line expansion.” arXiv preprint arXiv:2005.04843 (2020).

Hypergraph Metrics

Hypergraph metrics:

  1. matrix entropy

  2. average distance

  3. clustering coefficient

  4. nonlinear_eigenvector_centrality

HAT.metrics.matrix_entropy(HG, laplacian_type='Rodriguez')[source]

Computes hypergraph entropy based on the eigenvalues values of the Laplacian matrix.

Parameters:

laplacian_type (str, optional) – Type of hypergraph Laplacian matrix. This defaults to ‘Rodriguez’ and other choices inclue Bolla and Zhou (See: laplacianMatrix()).

Returns:

Matrix based hypergraph entropy

Return type:

float

Matrix entropy of a hypergraph is defined as the entropy of the eigenvalues of the hypergraph Laplacian matrix [1]. This may be applied to any version of the Laplacian matrix.

References

HAT.metrics.avgerage_distance(HG)[source]

Computes the average pairwise distance between any 2 vertices in the hypergraph.

Returns:

avgDist

Return type:

float

The hypergraph is clique expanded to a graph object, and the average shortest path on the clique expanded graph is returned.

HAT.metrics.clustering_coefficient(HG)[source]

Computes clustering average clustering coefficient of the hypergraph.

Returns:

average clustering coefficient

Return type:

float

For a uniform hypergraph, the clustering coefficient of a vertex \(v_i\) is defined as the number of edges the vertex participates in (i.e. \(deg(v_i)\)) divided by the number of \(k-`way edges that could exist among vertex :math:`v_i\) and its neighbors (See equation 31 in [1]). This is written

\[C_i = \frac{deg(v_i)}{\binom{|N_i|}{k}}\]

where \(N_i\) is the set of neighbors or vertices adjacent to \(v_i\). The hypergraph clustering coefficient computed here is the average clustering coefficient for all vertices, written

\[C=\sum_{i=1}^nC_i\]

References

HAT.metrics.degree_centrality(HG)[source]
HAT.metrics.nonlinear_eigenvector_centrality(HG, tol=0.0001, maxIter=3000, model='LogExp', alpha=10)[source]

Computes node and edge centralities.

Parameters:

  • tol (int, optional) – threshold tolerance for the convergence of the centrality measures, defaults to 1e-4

  • maxIter (int, optional) – maximum number of iterations for the centrality measures to converge in, defaults to 3000

  • model (str, optional) – the set of functions used to compute centrality. This defaults to ‘LogExp’, and other choices include ‘Linear’, ‘Max’ or a list of 4 custom function handles (See [1]).

  • alpha (int, optional) – Hyperparameter used for computing centrality (See [1]), defaults to 10

Returns:

vxcCentrality

Return type:

ndarray containing centrality scores for each vertex in the hypergraph

Returns:

edgeCentrality

Return type:

ndarray containing centrality scores for each edge in the hypergraph

References

Dynamics and Control

HAT.dynamics.ctrbk(HG, inputVxc)[source]

Compute the reduced controllability matrix for \(k-\) uniform hypergraphs.

Parameters:

inputVxc (ndarray) – List of vertices that may be controlled

Returns:

Controllability matrix

Return type:

ndarray

References

HAT.dynamics.b_matrix(HG, inputVxc)[source]

Constructs controllability \(B\) matrix commonly used in the linear control system

\[\frac{dx}{dt} = Ax+Bu\]
Parameters:

inputVxc (ndarray) – a list of input control nodes

Returns:

control matrix

Return type:

ndarray

References

HAT.HAT module

HAT.HAT.directSimilarity(HG1, HG2, measure='Hamming')[source]

This function computes the direct similarity between two uniform hypergraphs.

Parameters:

  • HG1 (Hypergraph) – Hypergraph 1

  • HG2 (Hypergraph) – Hypergraph 2

  • measure (str, optional) – This sepcifies which similarity measure to apply. It defaults to Hamming, and Spectral-S and Centrality are available as other options as well.

Returns:

Hypergraph similarity

Return type:

float

References

HAT.HAT.indirectSimilarity(G1, G2, measure='Hamming', eps=0.01)[source]

This function computes the indirect similarity between two hypergraphs.

Parameters:

  • G1 (nx.Graph or ndarray) – Hypergraph 1 expansion

  • G2 (nx.Graph or ndarray) – Hypergraph 2 expansion

  • measure (str, optional) – This specifies which similarity measure to apply. It defaults to Hamming , and Jaccard , deltaCon , Spectral , and Centrality are provided as well. When Centrality is used as the similarity measure, G1 and G2 should ndarray s of centrality values; Otherwise G1 and G2 are nx.Graph*s or *ndarray* s as adjacency matrices.

  • eps (float, optional) – a hyperparameter required for deltaCon similarity, defaults to 10e-3

Returns:

similarity measure

Return type:

float

References

HAT.HAT.multicorrelations(D, order, mtype='Drezner', idxs=None, v=False, vfreq=1000)[source]

This function computes the multicorrelation among pairwise or 2D data.

Parameters:

  • D (ndarray) – 2D or pairwise data

  • order (int) – order of the multi-way interactions

  • mtype (str) – This specifies which multicorrelation measure to use. It defaults to Drezner [1], but Wang [2] and Taylor [3] are options as well.

  • idxs (ndarray, optional) – specify which indices of D to compute multicorrelations of. The default is None, in which case all combinations of order indices are computed.

  • v (bool, optional) – verbose, defaults to False

  • vfreq – frequency to display output in verbose mode

Returns:

A vector of the multicorrelation scores computed and a vector of the column indices of D used to compute each multicorrelation.

Return type:

(ndarray, ndarray)

References

HAT.HAT.uniformErdosRenyi(v, e, k)[source]

This function generates a uniform, random hypergraph.

Parameters:

  • v (int) – number of vertices

  • e (int) – number of edges

  • k (int) – order of hypergraph

Returns:

Hypergraph

Return type:

Hypergraph

HAT.HAT.load(dataset='Karate')[source]

This function loads built-in datasets. Currently only one dataset is available and we are working to expand this.

Parameters:

dataset (str, optional) – sets which dataset to load in, defaults to ‘Karate’

Returns:

incidence matrix or graph object

Return type:

ndarray or nx.Graph

HAT.HAT.hyperedges2IM(edgeSet)[source]

This function constructs an incidence matrix from an edge set.

Parameters:

edgeSet (ndarray) – a \(e \times k\) matrix where each row contains \(k\) integers that are contained within the same hyperedge

Returns:

a \(n imes e\) incidence matrix where each row of the edge set corresponds to a column of the incidence matrix. \(n\) is the number of nodes contained in the edgeset.

Return type:

ndarray

HAT.HAT.hyperedgeHomophily(H, HG=None, G=None, method='CN')[source]

This function computes the hyperedge homophily score according to the below methods. The homophily score is the average score based on structural similarity of the vertices in hypredge H in the clique expanded graph G. This function is an interface from HAT to networkx link prediction algorithms.

Parameters:

  • G (networkx.Graph) – a pairwise hypergraph expansion

  • H (ndarray) – hyperedge containing individual vertices within the edge

  • method – specifies which structural similarity method to use. This defaults to CN common neighbors.

HAT.HAT.edgeRemoval(HG, p, method='Random')[source]
This function randomly removes edges from a hypergraph. In [1], four primary reasons are given for data missing in pairwise networks:

  1. random edge removal

  2. right censoring

  3. snowball effect

  4. cold-ends

This method removes edes from hypergraphs according to the multi-way analogue of these.

References

HAT.HAT.randomRemoval(HG, p)[source]
HAT.HAT.rightCensorRemoval(HG, p)[source]
HAT.HAT.coldEndsRemoval(HG, p)[source]
HAT.HAT.snowBallRemoval(HG, p)[source]

HAT.draw module

HAT.multilinalg module

HAT.multilinalg.hosvd(T, M=True, uniform=False, sym=False)[source]

Higher Order Singular Value Decomposition

Parameters:

  • uniform – Indicates if T is a uniform tensor

  • sym – Indicates if T is a super symmetric tensor

  • M – Indicates if the factor matrices are required as well as the core tensor

Returns:

The singular values of the core diagonal tensor and the factor matrices.

HAT.multilinalg.supersymHosvd(T)[source]

Computes the singular values of a uniform, symetric tensor. See Algorithm 1 in [1].

Parameters:

T – A uniform, symmetric multidimensional array

Returns:

The singular values that compose the core tensor of the HOSVD on T.

References

    1. Chen and I. Rajapakse, Tensor Entropy for Uniform Hypergraphs, IEEE TRANSACTIONS ON NETWORK SCIENCE AND ENGINEERING (2020)

HAT.multilinalg.HammingSimilarity(A1, A2)[source]

Computes the Spectral-S similarity of 2 Adjacency tensors [1].

Parameters:

  • A1 (ndarray) – adjacency tensor 1

  • A2 (ndarray) – adjacency tensor 2

Returns:

Hamming similarity measure

Return type:

float

References

  • Amit Surana, Can Chen, and Indika Rajapakse. Hypergraph similarity measures. IEEE Transactions on Network Science and Engineering, pages 1-16, 2022.

HAT.multilinalg.SpectralHSimilarity(L1, L2)[source]

Computes the Spectral-S similarity of 2 Laplacian tensors [1].

Parameters:

  • L1 (ndarray) – Laplacian tensor 1

  • L2 (ndarray) – Laplacian tensor 2

Returns:

Spectral-S similarity measure

Return type:

float

References

  • Amit Surana, Can Chen, and Indika Rajapakse. Hypergraph similarity measures. IEEE Transactions on Network Science and Engineering, pages 1-16, 2022.

HAT.multilinalg.kronecker_exponentiation(M, x)[source]

Kronecker Product Exponential.

Parameters:

  • M (ndarray) – a matrix

  • x (int) – power of exponentiation

Returns:

Krnoecker Product exponentiation of M a total of x times

Return type:

ndarray

This function performs the Kronecker Product on a matrix \(M\) a total of \(x\) times. The Kronecker product is defined for two matrices \(A\in\mathbf{R}^{l \times m}, B\in\mathbf{R}^{m \times n}\) as the matrix

\[\begin{split}A \bigotimes B= \begin{pmatrix} A_{1,1}B & A_{1,2}B & \dots & A_{1,m}B \\ A_{2,1}B & A_{2,2}B & \dots & A_{2,m}B \\ \vdots & \vdots & \ddots & \vdots \\ A_{l,1}B & A_{l,2}B & \dots & A_{l,n}B \end{pmatrix}\end{split}\]

Bug Reporting

Please report all bugs or defects in HAT to this page.