Heuristic Algorithm for Approximation Betweenness Centrality Using Graph Coarsening

Abstract

Nowadays, graph analytics are widely used in many research fields and applications. One important analytic that measures the influence of each vertex on flows through the network, is the betweenness centrality. It is used to analyze real-world networks like for example social networks and networks in computational biology. Unfortunately this centrality metric is rather expensive to compute and there is a number of studies devoted to approximate it. Here we focus on approximating the computation of betweenness centrality for dynamically changing graphs. We present a novel approach based on graph coarsening for approximating values of betweenness centrality, when new edges are inserted. Unlike other approaches, we reduce the cost (but not complexity) of the betweenness centrality computation step by working on a coarser graph. Our approach demonstrates more than 60% speedup compared to the exact recalculation of the betweenness centrality for dynamically changing graphs.