Hypergraphs

Hypergraphs generalize graphs to allow edges between more than two vertices. Like graphs, they come in directed and undirected flavors, but compared to graphs, hypergraphs are theoretically underdeveloped and poorly supported by software packages.

The study of hypergraphs has been driven mainly by applications involving relations or processes between more than two entities. For many of these applications, monoidal categories would be a better choice than hypergraphs. Nevertheless, hypergraphs have their uses. Also, monoidal categories and hypergraphs combine in hypergraph categories .

An elegant feature of hypergraphs, not possessed by graphs, is hypergraph duality: given a hypergraph, you get another hypergraph by exchanging the vertices and edges.

Software

  • R
    • hypergraph and hyperdraw on Bioconductor
    • hyperdraw uses Graphviz for layout but has custom rendering using R graphics

Literature

General, mostly or exclusively about undirected hypergraphs

  • Berge, 1989: Hypergraphs: Combinatorics of finite sets
    • Berge, 1976: Graphs and hypergraphs (pdf)
  • Voloshin, 2009: Introduction to graph and hypergraph theory
  • Bretto, 2013: Hypergraph theory (doi)
  • Brown, 2013: Discrete structures and their interactions, Ch. 5: Hypergraphs
  • Bahmanian & Šajna, 2015: Hypergraphs: connection and separation (doi, arxiv)
    • Sec. 1-2: All the basic definitions and a short literature review

Directed hypergraphs

  • Gallo et al, 1993: Directed hypergraphs and applications (doi)
    • Gallo & Scutella, 1998: Directed hypergraphs as a modelling paradigm (doi, tech report )
  • Klamt et al, 2009: Hypergraphs and cellular networks (doi, pdf)

Miscellaneous topics

  • Brault-Baron, 2016: Hypergraph acyclicity revisited (doi, arxiv)
    • Characterizes three notions of hypergraph acyclicity: alpha acyclicity, beta acyclicity, and gamma acyclicity
    • Alpha acyclicity describes acyclic queries, or rather their hypergraphs, in relational databases
  • Robeva & Seigal, 2018: Duality of graphical models and tensor networks (doi, arxiv)
    • Intriguing paper, which I have not yet read, showing that “the tensor hypernetwork on a hypergraph exactly corresponds to the graphical model given by the dual hypergraph”