Real world applications of hypergraphs

Question

A hypergraph is a graph generalization in which edge can connect many vertices. Recently I saw many publications about hypergraphs(segmentation, clustering and so on). So my questions is:

• Is there any real world applications of hypergraphs (and probably implementations) or this is just academic research that not intended to be used by engineers?
• Is there any analogs of the common graph algorithms, like max-flow or Dijkstra that can be used with hypergraphs?

I have an intuition about normal graphs. For example, graph can be used to represent transport network or busyness rules of Bayesian network. But I have no such intuition about hypergraphs, they're absolutely counterintuitive for me.

Answer 1

Hypergraphs are representable as bipartite graphs, and bipartite graphs can be used to construct a hypergraph. This is really just saying that you can represent interactions between some form of actors either as vertices or as (hyper-)edges.

Once we recognize this equivalence, we can then conclude that hypergraphs are usable when you might otherwise use a bipartite graph, and that the analogs of graph algorithms are more directly to algorithms on bipartite graphs.

Answer 2

There is a nice for image clustering using a hypergraph: http://vision.ucsd.edu/bpc/

The slides are here: http://vision.ucsd.edu/~sagarwal/bpc_cvpr05_slides.pdf

Although the algorithm did not become mainstream, it is an elegant illustration of the idea of links in hypergaphs and their meaning. I think that hypergraphs might be very useful in data mining.

Answer 3

Mathematical models of product assembly from parts are based on hypergraphs. This is used in Computer-aided Manufacturing (CAM) systems to determine possible and optimal (in some sense) orders of assembly.