Betweenness computation in the single graph representation of 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.