2023/07/21 by Michael Rawson, Audun Myers, Rawson, Michael G. +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #05C65 #06B99 #68P01 #Bayesian Modeling and Causal Inference #Bioinformatics and Genomic Networks #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Rough Sets and Fuzzy Logic
paper · pdf · doi:10.48550/arxiv.2307.11681
openalex publication_date 2023/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
There is increasing focus on analyzing data represented as hypergraphs, which are better able to express complex relationships amongst entities than are graphs. Much of the critical information about hypergraph structure is available only in the intersection relationships of the hyperedges, and so forming the "intersection complex" of a hypergraph is quite valuable. This identifies a valuable isomorphism between the intersection complex and the "concept lattice" formed from taking the hypergraph's incidence matrix as a "formal context": hypergraphs also generalize graphs in that their incidence matrices are arbitrary Boolean matrices. This isomorphism allows connecting discrete algorithms for lattices and hypergraphs, in particular s-walks or s-paths on hypergraphs can be mapped to order theoretical operations on the concept lattice. We give new algorithms for formal concept lattices and hypergraph s-walks on concept lattices. We apply this to a large real-world dataset and find deep lattices implying high interconnectivity and complex geometry of hyperedges.