First, let’s have a look at an image—hopefully telling us more than a thousand words:
Okay, let’s go back to square one—before you understand hypergraphs, we first need to understand graphs.
What Are Graphs?
You most likely know graphs.
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.
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.
Deepen your conceptual code understanding with the Finxter web app.
Academy Course – Mastering the Top 10 Graph Algorithms
If you want to improve your fundamental computer science skills, there’s nothing more effective than studying algorithms.
To help you master the most important graph algorithms, we’ve just launched the “Top 10 Algorithms” course at the Finxter Computer Science Academy. This great course from Finxter Star Creator Matija ⭐ teaches you the most important graph algorithms such as BFS, DFS, A*, and Dijkstra.
Understanding these algorithms will not only make you a better coder, but it’ll also lay a strong foundation on which you can build your whole career as a computer scientist.
Click the screenshot to find out more:
