Hypergraph

Definition of a Hypergraph

A mathematical abstract structure consisting of a set of vertices and set of hyperedges which can connect any number of vertices.

Generalised as

set

Specialised into

ordinary graph (+ pair of vertices)

Hypergraph vs Graph

While graph edges are pairs of vertices, hyperedges of a hypergraph contain an arbitrary number of vertices.

Visualisation

Hypergraphs can be visualised in different ways. Colours are often used to increase readability. A hypergraph can also be represented as an incidence matrix.

different representations hypergraph — Figure 1. Ordinary graph (a) and hypergraph with 3 (hyper)edges represented as a network (b), Venn diagram (c) and incidence matrix (d).

Related Terms

hyperedge, k-uniform

Examples

Undirected hypergraphs: organisation diagram, recommender system, image retrieval, bioinformatics.

Directed hypergraphs: fraud, operations research, transportation planning.

Examples hypergraph — Figure 2. An organisation diagram and circuit diagram are examples of a hypergraph.

Incidence matrix graph vs hypergraph — Figure 3. Comparison incidence matrix representation of the same data as ordinary graph (a)
and a more compact hypergraph (b) [1].

Reference

[1] Valdivia, P., Buono, P., Plaisant, C., Dufournaud, N., & Fekete, J. D. (2019). Analysing dynamic hypergraphs with parallel aggregated ordered hypergraph visualisation. IEEE transactions on visualisation and computer graphics, 27(1), 1-13.