Fast Approximated Betweenness Centrality of Directed and Weighted Graphs

Node betweenness centrality is a reference metric to identify the most critical spots of a network. However, its exact computation exhibits already high (time) complexity on unweighted, undirected graphs. In some domains such as transportation, weighted and directed graphs can provide more realistic modeling, but at the cost of an additional computation burden that limits the adoption of betweenness centrality for real-time monitoring of large networks. As largely demonstrated in previous work, approximated approaches represent a viable solution for continuous monitoring of the most critical nodes of large networks, when the knowledge of the exact values is not necessary for all the nodes. This paper presents a fast algorithm for approximated computation of betweenness centrality for weighted and directed graphs. It is a substantial extension of our previous work which focused only on unweighted and undirected networks. Similarly to that, it is based on the identification of pivot nodes that equally contribute to betweenness centrality values of the other nodes of the network. The pivots are discovered via a cluster-based approach that permits to identify the nodes that have the same properties with reference to clusters’ border nodes. The results prove that our algorithm exhibits significantly lower execution time and a bounded and tolerable approximation with respect to state-of-the-art approaches for exact computation when applied to very large, weighted and directed graphs.