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.

Cheeseburger

I found this topic on math overflow - mathoverflow.net/questions/13750/… but it discuses mathematical application, not algorithmic. – Cheeseburger

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.

Kalahari

Answer 2

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.

Diamagnetic

Answer 3

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.

Inamorata

Answer 4

^{Figure 1 - Representations of higher-order interactions from Battiston et. al [1]}

Hypergraph

Hypergraphs are a useful data representation when considering group interactions. Consider a authorship network where a group of authors - i.e., Author-A, Author-B, and Author-C who have co authored in a single publication. Representing this information using traditional graph edges where each edge connects two authors to show the co-authorship relationships bring two issues. First, it introduces misleading information where we can not differentiate the case of a single publication by three authors; and three authors co-authored three publications among them (i.e. Publication-1 co-authored by Author-A and Author-B; Publication-2 co-authored by Author-B and Author-C; Publication-3 co-authored by Author-A and Author-C). The second implication of representing hypergraph using traditional graph representation is the inflation of data in the graph storage. For example in our previous co-authorship network, we will need to add N*(N-1) edges to represent the co-authorship among N authors for a single publication. By learning how to encode data into these structures and how to manipulate them to extract meaningful data, we may be able to gain insights about the data that would have not been possible before.

^{Figure 2 - An example hypergraph representing the groups {0,1,2}, {1,2,3}, and {0,3}, and its bipartite representation from [2]}

Hypergraph Algorithms

Pagerank

Pagerank is a commonly used graph analytic algorithm. It is used to find the relative importance of the vertices in a network. There are a wide range of applications where pagerank plays very important roles, for example in recommendation systems, link prediction, search engines, etc. We can think of the implication of pagerank in hypergraphs in two different ways. First, the importance of vertices in a network based on their group participation. For example, in a social network context we can measure the importance of a user based on the group membership, e.g., admin of a group with a minion of users might have a bigger influence in the whole network. Second, the importance of the hyperedges based on the vertices it is linked to. For example, from a co-authorship network we can find the most influential publications based on the relative importance of the authors in the network.

Reference

1. Battiston, F., Cencetti, G., Iacopini, I., Latora, V., Lucas, M., Patania, A., Young, J.-G., & Petri, G. (2020). Networks beyond pairwise interactions: Structure and dynamics. Physics Reports. https://doi.org/10.1016/j.physrep.2020.05.004
2. Julian Shun. 2020. Practical parallel hypergraph algorithms. In Proceedings of the 25th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '20). Association for Computing Machinery, New York, NY, USA, 232–249. DOI:https://doi.org/10.1145/3332466.3374527
3. Abdullah Al Raqibul Islam, An experimental code of hypergraph PageRank implementation using Apache Spark., (2021), GitHub repository, https://github.com/biqar/hypergraph-study

Minna