Hypergraph

See: Graph, Hyperedge, Hypercube.

---

---

References

2011

• (Wikipedia, 2011) ⇒ http://en.wikipedia.org/wiki/Hypergraph
  • QUOTE: In mathematics, a hypergraph is a generalization of a graph, where an edge can connect any number of vertices. Formally, a hypergraph [math]\displaystyle{ H }[/math] is a pair [math]\displaystyle{ H = (X,E) }[/math] where [math]\displaystyle{ X }[/math] is a set of elements, called nodes or vertices, and [math]\displaystyle{ E }[/math] is a set of non-empty subsets of [math]\displaystyle{ X }[/math] called hyperedges or links. Therefore, [math]\displaystyle{ E }[/math] is a subset of [math]\displaystyle{ \mathcal{P}(X) \setminus\{\emptyset\} }[/math], where [math]\displaystyle{ \mathcal{P}(X) }[/math] is the power set of [math]\displaystyle{ X }[/math].

    While graph edges are pairs of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain an arbitrary number of nodes. However, it is often useful to study hypergraphs where all hyperedges have the same cardinality: a k-uniform hypergraph is a hypergraph such that all its hyperedges have size k. (In other words, it is a collection of sets of size k.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of triples, and so on.

    A hypergraph is also called a set system or a family of sets drawn from the universal set X. Hypergraphs can be viewed as incidence structures and vice versa. In particular, there is a Levi graph corresponding to every hypergraph, and vice versa. In computational geometry, a hypergraph may be called a range space and the hyperedges are called ranges.

    In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory.

    Special cases of hypergraphs include the clutter, where no edge appears as a subset of another edge; and the abstract simplicial complex, which contains all subsets of every edge.

    The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.

2009

• (Kok & Domingos, 2009) ⇒ Stanley Kok, and Pedro Domingos. (2009). “Learning Markov Logic Network Structure via Hypergraph Lifting.” In: Proceedings of ICML 2009.
  • QUOTE: … A relational database can be viewed as a hypergraph with constants as nodes and relations as hyperedges. We find paths of true ground atoms in the hypergraph that are connected via their arguments. To make this tractable (there are exponentially many paths in the hypergraph), we lift the hypergraph by jointly clustering the constants to form higher-level concepts, and find paths in it.

---