Getting started with hypergraphs

What are hypergraphs?

In mathematics, a hypergraph is a generalization of a graph in which an edge can connect any number of vertices. -- wikipedia

In other words, hypergraph is a tuple of set of hyperedges (sets of vertices) and set of vertices.


There exists a theorem that every hypergraph H may be represented by a bipartite graph BG:

bipartite graph

the sets X and E are the partitions 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.

In simple words, to get a coresponding bipartite graph, get nodes of hypergraph - lets call them U, get all the hyperedges, convert them to nodes, naming them after the nodes they link - they are now the second set of nodes, V. Having two groups of nodes, connect former hyperedges (now, members of set V) with the nodes they linked in hypergraph. Every member of V is connected only with members of U, and other way round. It's a definition of a bipartite graph!


My thesis is modelling difussion on hypergraphs. Hypergraphs are very useful structures and they're used in many applications. There are some examples from mathoverflow.

However I think that they're much less known than graphs. I even had some problems to find books about them in my university library...

If you're interested in learning hypergraph theory, there are some books on the amazon which are great introduction.

Representation of hypergraphs

I was looking for a good library for representing hypergraphs in the internet, but I haven't found anything satisfatory. There are lots of tools for graphs instead. And it wasn't only my problem, I found this question on stackoverflow - which asks for tools. However answers aren't any good, question linked to a paper about visualization of hypergraphs - Visualization of Hyperedges in Fixed Graph Layouts (PDF) which looks really promising.

I plan to develop my own python library/package to visualize hypergraphs using the excellent matplotlib library.

Programming hypergraphs

To program hypergraphs I use NetworkX library which is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and functions of complex networks.

NetworkX is really great. It's easy to use, open source (BSD license), it has plenty of useful functionalities, well written documentation, tutorial and gallery of examples.

To start my programming adventure with hypergraphs I used ipython notebook. You can see it here. Here is also a whole github repository of my work. I'm just getting started though, so it's not so perfect as I would like it to be.

Posted: | Source
Comments powered by Disqus