Scalability Analysis of Cluster-based Betweenness Computation in Large Weighted Graphs.

Computation of node betweenness centrality (BC) of weighted and directed graphs is a time-consuming task that could limit the application of such a metric for monitoring large, dynamic networks. As widely demonstrated in previous work, approximated approaches represent a solution to reduce computation time when ranking nodes according to their BC values is sufficient with respect to knowing their exact BC values. According to this observation, we have proposed a fast algorithm for computing approximated BC values for large weighted and directed graphs. It is based on the identification of pivot nodes that equally contribute to BC values of the other nodes of the network discovered via a cluster-based approach.In this paper, we focus on the performance and scalability analysis of the proposed algorithm in order to characterize its behavior with different sets of computing resources and to identify room for further improvements. To this end, we exploit a real dataset related to a transportation network. The results show that the proposed algorithm exhibits significantly lower execution times if compared with the Brandes's solution for computing exact BC values, especially when the number of available computing resources is limited. However, the speedup is not negligible even when the number of resources grows, where improvements are possible, as shown by our analysis.