Computing hypergraph homology
Xiang Liu, Huitao Feng, Jie Wu, Kelin Xia · Foundations of Data Science · 2024
As a generalization of graphs and simplicial complexes, hypergraphs have various applications in chemistry, biology, computer science and data science. Recently, the first well-defined hypergraph-based embedded homology and persistent (embedded) homology models have been proposed and achieved great success in drug design. However, the further applications of these models have been significantly hindered by the lack of efficient computational algorithms. In this paper, we propose an algorithm for embedded homology and persistent (embedded) homology of hypergraphs over field coefficient. One of the key issues for hypergraph-based homology models is the absence of proper boundary operators as in traditional simplicial complex-based models. A supremum/infimum chain complex has been proposed in the embedded homology model with well-defined boundary operators. Here we give detailed algorithms for transforming a filtered hypergraph to its filtered infimum chain complex and supremum chain complex. In this way, the general algorithm for chain complex can be used directly on the supremum/infimum chain complexes. Our algorithm has been validated on hypergraph models of protein structures from the protein data bank. It has been found that our algorithm is very robust and efficient.