In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices.
Formally, a directed hypergraph is a pair
(X,E)
X
E
X
(D,C)\inE
D
C
The order of a hypergraph
(X,E)
X
E
e=(D,C)
|e|=(|D|,|C|)
The definition above generalizes from a directed graph to a directed hypergraph by defining the head or tail of each edge as a set of vertices (
C\subseteqX
D\subseteqX
|e|
Under one definition, an undirected hypergraph
(X,E)
(D,C)\inE
(C,D)\inE
(D,C)\inE
(C,D)\vec{\in}E
\vec{\in}
While graph edges connect only 2 nodes, hyperedges connect an arbitrary number of nodes. However, it is often desirable 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, one such hypergraph is a collection of sets, each such set a hyperedge connecting k nodes.) So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on. An undirected hypergraph is also called a set system or a family of sets drawn from the universal set.
Hypergraphs can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, every bipartite graph can be regarded as the incidence graph of a hypergraph when it is 2-colored and it is indicated which color class corresponds to hypergraph vertices and which to hypergraph edges.
Hypergraphs have many other names. In computational geometry, an undirected hypergraph may sometimes be called a range space and then the hyperedges are called ranges.[1] In cooperative game theory, hypergraphs are called simple games (voting games); this notion is applied to solve problems in social choice theory. In some literature edges are referred to as hyperlinks or connectors.[2]
The collection of hypergraphs is a category with hypergraph homomorphisms as morphisms.
Undirected hypergraphs are useful in modelling such things as satisfiability problems,[3] databases, machine learning, and Steiner tree problems.[4] They have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics). The applications include recommender system (communities as hyperedges), image retrieval (correlations as hyperedges), and bioinformatics (biochemical interactions as hyperedges). Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian, and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results. For large scale hypergraphs, a distributed framework built using Apache Spark is also available.
Directed hypergraphs can be used to model things including telephony applications,[5] detecting money laundering,[6] operations research,[7] and transportation planning. They can also be used to model Horn-satisfiability.
Many theorems and concepts involving graphs also hold for hypergraphs, in particular:
In directed hypergraphs: transitive closure, and shortest path problems.
Although hypergraphs are more difficult to draw on paper than graphs, several researchers have studied methods for the visualization of hypergraphs.
In one possible visual representation for hypergraphs, similar to the standard graph drawing style in which curves in the plane are used to depict graph edges, a hypergraph's vertices are depicted as points, disks, or boxes, and its hyperedges are depicted as trees that have the vertices as their leaves.[8] [9] If the vertices are represented as points, the hyperedges may also be shown as smooth curves that connect sets of points, or as simple closed curves that enclose sets of points.[10] [11] [12]
In another style of hypergraph visualization, the subdivision model of hypergraph drawing,[13] the plane is subdivided into regions, each of which represents a single vertex of the hypergraph. The hyperedges of the hypergraph are represented by contiguous subsets of these regions, which may be indicated by coloring, by drawing outlines around them, or both. An order-n Venn diagram, for instance, may be viewed as a subdivision drawing of a hypergraph with n hyperedges (the curves defining the diagram) and 2n − 1 vertices (represented by the regions into which these curves subdivide the plane). In contrast with the polynomial-time recognition of planar graphs, it is NP-complete to determine whether a hypergraph has a planar subdivision drawing,[14] but the existence of a drawing of this type may be tested efficiently when the adjacency pattern of the regions is constrained to be a path, cycle, or tree.[15]
An alternative representation of the hypergraph called PAOH is shown in the figure on top of this article. Edges are vertical lines connecting vertices. Vertices are aligned on the left. The legend on the right shows the names of the edges. It has been designed for dynamic hypergraphs but can be used for simple hypergraphs as well.
Classic hypergraph coloring is assigning one of the colors from set
\{1,2,3,...,λ\}
Hypergraphs for which there exists a coloring using up to k colors are referred to as k-colorable. The 2-colorable hypergraphs are exactly the bipartite ones.
There are many generalizations of classic hypergraph coloring. One of them is the so-called mixed hypergraph coloring, when monochromatic edges are allowed. Some mixed hypergraphs are uncolorable for any number of colors. A general criterion for uncolorability is unknown. When a mixed hypergraph is colorable, then the minimum and maximum number of used colors are called the lower and upper chromatic numbers respectively.[16]
A hypergraph can have various properties, such as:
d
d
d
k
k
k
k
k
k\geq2
k
Because hypergraph links can have any cardinality, there are several notions of the concept of a subgraph, called subhypergraphs, partial hypergraphs and section hypergraphs.
Let
H=(X,E)
X=\lbracexi\midi\inIv\rbrace,
and having edge set
E=\lbraceei\midi\inIe,ei\subseteqX,ei ≠ \emptyset\rbrace,
where
Iv
Ie
A subhypergraph is a hypergraph with some vertices removed. Formally, the subhypergraph
HA
A\subseteqX
HA=\left(A,\lbracee\capA\mide\inE,e\capA ≠ \emptyset\rbrace\right).
An alternative term is the restriction of H to A.
An extension of a subhypergraph is a hypergraph where each hyperedge of
H
HA
Ex(HA)
Ex(HA)=(A\cupA',E')
A'=cupee\setminusA
E'=\lbracee\inE\mide\subseteq(A\cupA')\rbrace
The partial hypergraph is a hypergraph with some edges removed. Given a subset
J\subsetIe
J
\left(X,\lbraceei\midi\inJ\rbrace\right).
Given a subset
A\subseteqX
H x A=\left(A,\lbraceei\midi\inIe,ei\subseteqA\rbrace\right).
H*
H
\lbraceei\rbrace
\lbraceXm\rbrace
Xm=\lbraceei\midxm\inei\rbrace.
When a notion of equality is properly defined, as done below, the operation of taking the dual of a hypergraph is an involution, i.e.,
\left(H*\right)*=H.
A connected graph G with the same vertex set as a connected hypergraph H is a host graph for H if every hyperedge of H induces a connected subgraph in G. For a disconnected hypergraph H, G is a host graph if there is a bijection between the connected components of G and of H, such that each connected component G' of G is a host of the corresponding H'.
The 2-section (or clique graph, representing graph, primal graph, Gaifman graph) of a hypergraph is the graph with the same vertices of the hypergraph, and edges between all pairs of vertices contained in the same hyperedge.
Let
V=\{v1,v2,~\ldots,~vn\}
E=\{e1,e2,~\ldots~em\}
n x m
For an undirected hypergraph,
I=(bij)
bij=\left\{\begin{matrix}1&if~vi\inej\ 0&otherwise.\end{matrix}\right.
It
H*=(V*, E*)
H
V*
E*
V*
| * | |
| v | |
| j |
\inV*
| * | |
| e | |
| i |
\inE*,~
| * | |
| v | |
| j |
\in
| * | |
| e | |
| i |
bij=1
For a directed hypergraph, the heads and tails of each hyperedge
ej
H(ej)
T(ej)
I=(bij)
bij=\left\{\begin{matrix}-1&if~vi\inT(ej)\ 1&if~vi\inH(ej)\ 0&otherwise.\end{matrix}\right.
A hypergraph H may be represented by a bipartite graph BG as follows: the sets X and E are the parts of BG, and (x1, e1) are connected with an edge if and only if vertex x1 is contained in edge e1 in H.
Conversely, any bipartite graph with fixed parts and no unconnected nodes in the second part represents some hypergraph in the manner described above. This bipartite graph is also called incidence graph.
A parallel for the adjacency matrix of a hypergraph can be drawn from the adjacency matrix of a graph. In the case of a graph, the adjacency matrix is a square matrix which indicates whether pairs of vertices are adjacent. Likewise, we can define the adjacency matrix
A=(aij)
ek
| w | |
| ek |
\in\R
aij=\left\{\begin{matrix}
| w | |
| ek |
&if~(vi,vj)\inE\ 0&otherwise.\end{matrix}\right.
In contrast with ordinary undirected graphs for which there is a single natural notion of cycles and acyclic graphs, there are multiple natural non-equivalent definitions of acyclicity for hypergraphs which collapse to ordinary graph acyclicity for the special case of ordinary graphs.
A first definition of acyclicity for hypergraphs was given by Claude Berge:[19] a hypergraph is Berge-acyclic if its incidence graph (the bipartite graph defined above) is acyclic. This definition is very restrictive: for instance, if a hypergraph has some pair
v ≠ v'
f ≠ f'
v,v'\inf
v,v'\inf'
We can define a weaker notion of hypergraph acyclicity,[20] later termed α-acyclicity. This notion of acyclicity is equivalent to the hypergraph being conformal (every clique of the primal graph is covered by some hyperedge) and its primal graph being chordal; it is also equivalent to reducibility to the empty graph through the GYO algorithm[21] [22] (also known as Graham's algorithm), a confluent iterative process which removes hyperedges using a generalized definition of ears. In the domain of database theory, it is known that a database schema enjoys certain desirable properties if its underlying hypergraph is α-acyclic.[23] Besides, α-acyclicity is also related to the expressiveness of the guarded fragment of first-order logic.
We can test in linear time if a hypergraph is α-acyclic.[24]
Note that α-acyclicity has the counter-intuitive property that adding hyperedges to an α-cyclic hypergraph may make it α-acyclic (for instance, adding a hyperedge containing all vertices of the hypergraph will always make it α-acyclic). Motivated in part by this perceived shortcoming, Ronald Fagin[25] defined the stronger notions of β-acyclicity and γ-acyclicity. We can state β-acyclicity as the requirement that all subhypergraphs of the hypergraph are α-acyclic, which is equivalent to an earlier definition by Graham. The notion of γ-acyclicity is a more restrictive condition which is equivalent to several desirable properties of database schemas and is related to Bachman diagrams. Both β-acyclicity and γ-acyclicity can be tested in polynomial time.
Those four notions of acyclicity are comparable: Berge-acyclicity implies γ-acyclicity which implies β-acyclicity which implies α-acyclicity. However, none of the reverse implications hold, so those four notions are different.
A hypergraph homomorphism is a map from the vertex set of one hypergraph to another such that each edge maps to one other edge.
A hypergraph
H=(X,E)
G=(Y,F)
H\simeqG
\phi:X\toY
\pi
I
\phi(ei)=f\pi(i)
The bijection
\phi
H\simeqG
H*\simeqG*
When the edges of a hypergraph are explicitly labeled, one has the additional notion of strong isomorphism. One says that
H
G
H\congG
When the vertices of a hypergraph are explicitly labeled, one has the notions of equivalence, and also of equality. One says that
H
G
H\equivG
\phi
\phi(xn)=yn
and
\phi(ei)=f\pi(i)
Note that
H\equivG
H*\congG*
If, in addition, the permutation
\pi
H
G
H=G
\left(H*\right)*=H
A hypergraph automorphism is an isomorphism from a vertex set into itself, that is a relabeling of vertices. The set of automorphisms of a hypergraph H (= (X, E)) is a group under composition, called the automorphism group of the hypergraph and written Aut(H).
Consider the hypergraph
H
H=\lbrace e1=\lbracea,b\rbrace, e2=\lbraceb,c\rbrace, e3=\lbracec,d\rbrace, e4=\lbraced,a\rbrace, e5=\lbraceb,d\rbrace, e6=\lbracea,c\rbrace \rbrace
G=\lbrace f1=\lbrace\alpha,\beta\rbrace, f2=\lbrace\beta,\gamma\rbrace, f3=\lbrace\gamma,\delta\rbrace, f4=\lbrace\delta,\alpha\rbrace, f5=\lbrace\alpha,\gamma\rbrace, f6=\lbrace\beta,\delta\rbrace \rbrace
Then clearly
H
G
\phi(a)=\alpha
H
a
e1\cape4\cape6=\lbracea\rbrace
In graph
G
f1\capf4\capf6=\varnothing
In this example,
H
G
H\equivG
H*\congG*
The
r(H)
H
The degree d(v) of a vertex v is the number of edges that contain it. H is k-regular if every vertex has degree k.
The dual of a uniform hypergraph is regular and vice versa.
Two vertices x and y of H are called symmetric if there exists an automorphism such that
\phi(x)=y
ei
ej
\phi(ei)=ej
A hypergraph is said to be vertex-transitive (or vertex-symmetric) if all of its vertices are symmetric. Similarly, a hypergraph is edge-transitive if all edges are symmetric. If a hypergraph is both edge- and vertex-symmetric, then the hypergraph is simply transitive.
Because of hypergraph duality, the study of edge-transitivity is identical to the study of vertex-transitivity.
A partition theorem due to E. Dauber[26] states that, for an edge-transitive hypergraph
H=(X,E)
(X1,X2, … ,XK)
of the vertex set
X
| H | |
| Xk |
Xk
1\lek\leK
| K | |
| \sum | |
| k=1 |
| r\left(H | |
| Xk |
\right)=r(H)
where
r(H)
As a corollary, an edge-transitive hypergraph that is not vertex-transitive is bicolorable.
Graph partitioning (and in particular, hypergraph partitioning) has many applications to IC design and parallel computing.[27] Efficient and scalable hypergraph partitioning algorithms are also important for processing large scale hypergraphs in machine learning tasks.[28]
One possible generalization of a hypergraph is to allow edges to point at other edges. There are two variations of this generalization. In one, the edges consist not only of a set of vertices, but may also contain subsets of vertices, subsets of subsets of vertices and so on ad infinitum. In essence, every edge is just an internal node of a tree or directed acyclic graph, and vertices are the leaf nodes. A hypergraph is then just a collection of trees with common, shared nodes (that is, a given internal node or leaf may occur in several different trees). Conversely, every collection of trees can be understood as this generalized hypergraph. Since trees are widely used throughout computer science and many other branches of mathematics, one could say that hypergraphs appear naturally as well. So, for example, this generalization arises naturally as a model of term algebra; edges correspond to terms and vertices correspond to constants or variables.
For such a hypergraph, set membership then provides an ordering, but the ordering is neither a partial order nor a preorder, since it is not transitive. The graph corresponding to the Levi graph of this generalization is a directed acyclic graph. Consider, for example, the generalized hypergraph whose vertex set is
V=\{a,b\}
e1=\{a,b\}
e2=\{a,e1\}
b\ine1
e1\ine2
b\ine2
Alternately, edges can be allowed to point at other edges, irrespective of the requirement that the edges be ordered as directed, acyclic graphs. This allows graphs with edge-loops, which need not contain vertices at all. For example, consider the generalized hypergraph consisting of two edges
e1
e2
e1=\{e2\}
e2=\{e1\}
The generalized incidence matrix for such hypergraphs is, by definition, a square matrix, of a rank equal to the total number of vertices plus edges. Thus, for the above example, the incidence matrix is simply
\left[\begin{matrix}0&1\ 1&0\end{matrix}\right].