What is a Hypergraph?

Hypergraph Example

Graphs

You most likely know graphs.

The web graph example

The web graph consists of websites connected via hyperlinks. The websites are graph vertices and the hyperlinks are graph edges. Each graph edge connects exactly two vertices.

What happens if you drop this limitation and allow each edge to connect an arbitrary number of vertices? Simple: you get a hypergraph.

Hypergraphs

In the hypergraph, each hyperedge connects an arbitrary number of hypervertices instead of only two. So, the hypergraph model allows you to model group relations instead of only binary relations.

Graph vs Hypergraph

Formally, a hypergraph is defined as a tuple H = (V, E) where

  • V is the set of hypervertices, and
  • E is the set of hyperedges. Mathematically, it’s a set of a set—each inner set representing an n-to-n relationship: n = |V| vertices are connected to n other vertices in the same group (including themselves).

One of the most popular research papers on hypergraphs provides the following two ways of modeling them:

  • Adjacency matrix: each cell connects one vertex (row) to one hyperedge (column). You can see this on the left of the following graphic.
  • Set-based model: each hyperedge corresponds to a set of vertices. You can see this on the right of the following graphic.

Examples Real-World Hypergraphs

  • WhatsApp is a group-based communication technology. The group sizes race from two to thousands of members. Thus, hypergraphs are an excellent modeling abstraction for the WhatsApp social network.
  • Facebook Groups are another example. The Facebook users are the hypervertices. Each Facebook user belongs to zero or more Facebook Groups. Each group can be modeled by a hyperedge connecting multiple users with each other.
  • Real-world Social Networks can also be structured as hypergraphs: people are hypervertices and organizations are hyperedges. Each person belongs to an arbitrary number of organizations and is connected to other users in the same organizations via the hyperedge representing it.

All graph applications are also applications of hypergraphs because graphs are just special cases of hypergraphs (with the restriction of having only binary versus n-ary vertex relations).

Relationship with Bipartite Graphs

Hypergraphs and bipartite graphs are related in that a hypergraph can be modeled with a bipartite graph and bipartite graphs, generally, can be modeled with a hypergraph.

However, they are not isomorphic because some bipartite graphs cannot be modeled sufficiently by a hypergraph: The hypergraph data structure doesn’t allow for directed edges but the bipartite graph does.

Hypergraph vs Bipartite Graph

Deepen your conceptual code understanding with the Finxter web app.

Leave a Comment