Hypergraph
While graph edges are 2-element subsets of nodes, hyperedges are arbitrary sets of nodes, and can therefore contain 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.
So a 2-uniform hypergraph is a graph, a 3-uniform hypergraph is a collection of unordered triples, and so on
Hypergr aph s can be viewed as incidence structures. In particular, there is a bipartite "incidence graph" or "Levi graph" corresponding to every hypergraph, and conversely, most, but not all, bipartite graphs can be regarded as incidence graphs of hypergraphs.
In computational geometry, a hypergraph may sometimes be called a range space and then the hyperedges are called ranges.
k {\displaystyle k}-partite - the vertices are partitioned into k {\displaystyle k} parts, and each hyperedge contains precisely one vertex of each type. Every k {\displaystyle k} -partite hypergraph (for k ≥ 2 {\displaystyle k≥ 2} ) is both k {\displaystyle k} -uniform and bipartite (and 2-colorable).
One possible generalization of a hypergraph is to allow edges to point at other edges.
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.
Hypergraphs have been extensively used in machine learning tasks as the data model and classifier regularization (mathematics)
The applications include recommender system (communities as hyperedges),[27]image retrieval (correlations as hyperedges),[28] and bioinformatics (biochemical interactions as hyperedges).[29] Representative hypergraph learning techniques include hypergraph spectral clustering that extends the spectral graph theory with hypergraph Laplacian,[30] and hypergraph semi-supervised learning that introduces extra hypergraph structural cost to restrict the learning results.[31] For large scale hypergraphs, a distributed framework[17] built using Apache Spark is also available.
