Linearization of Dependency and Sampling for Participation-based Betweenness Centrality in Very Large B-hypergraphs

Abstract

A B-hypergraph consisting of nodes and directed hyperedges is a generalization of the directed graph. A directed hyperedge in the B-hypergraph represents a relation from a set of source nodes to a single destination node. We suggest one possible definition of betweenness centrality (BC) in B-hypergraphs, called Participation-based BC (PBC). A PBC score of a node is computed based on the number of the shortest paths in which the node participates. This score can be expressed in terms of dependency on the set of its outgoing hyperedges. In this article, we focus on developing efficient computation algorithms for PBC. We first present an algorithm called ePBC for computing exact PBC scores of nodes, which has a cubic-time complexity. This algorithm, however, can be used for only small-sized B-hypergraphs because of its cubic-time complexity, so we propose linearized PBC (ℓPBC) that is an approximation method of ePBC. ℓPBC that comes with a guaranteed upper bound on its error, uses a linearization of dependency on a set of hyperedges. ℓPBC improves the computing time of ePBC by an order of magnitude (i.e., it requires a quadratic time) while maintaining a high accuracy. ℓPBC works well on small to medium-sized B-hypergraphs, but is not scalable enough for a very large B-hypergraph with more than a million hyperedges. To cope with such a very large B-hypergraph, we propose a very fast heuristic sampling-based method called sampling-based ℓPBC (sℓPBC). We show through extensive experiments that ℓPBC and sℓPBC can efficiently estimate PBC scores in various real-world B-hypergraphs with a reasonably good precision@k. The experimental results show that sℓPBC works efficiently even for a very large B-hypergraph.