Betweenness computation in the single graph representation of hypergraphs

• We present algorithms for computing betweenness centrality on hypergraphs.
• Forward and backpropagation are modified to avoid redundant computation.
• Vertices that belong to a single hyperedge can be merged without compromising the computation accuracy.
• Betweenness centrality can be computed orders of magnitude faster on real hypergraphs.

Many real-world social networks are hypergraphs because they either explicitly support membership in groups or implicitly include communities. We present the HyperBC algorithm that exactly computes betweenness centrality (or BC) in hypergraphs. The forward phase of HyperBC and the backpropagation phase are specifically tailored for BC computation on hypergraphs. In addition, we present an efficient method for pruning networks through the notion of “non-bridging” vertices. We experimentally evaluate our algorithm on a variety of real and artificial networks and show that it significantly speeds up the computation of BC on both real and artificial hypergraphs, while at the same time, being very memory efficient.