Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs

Mostafa Haghir Chehreghani (1, 2) , Albert Bifet (1, 2) , Talel Abdessalem (1, 2)

1 DIG - Data, Intelligence and Graphs
2 INFRES - Département Informatique et Réseaux

In this paper, first given a directed network G and a vertex r \in V(G) , we propose a new exact algorithm to compute betweenness score of r. Our algorithm pre-computes a set {RF}(r), which is used to prune a huge amount of computations that do not contribute in the betweenness score of r. Then, for the cases where {RF}(r) is large, we present a randomized algorithm that samples from {RF}(r) and performs computations for only the sampled elements. We show that this algorithm provides (\epsilon ,\delta ) an -approximation of the betweenness score of r. Finally, we empirically evaluate our algorithms and show that they significantly outperform the most efficient existing algorithms, in terms of both running time and accuracy. Our experiments also show that our proposed algorithms can effectively compute betweenness scores of all vertices in a set of vertices.

Mots clés: Directed graphs; Betweenness centrality; Exact algorithm; Approximate algorithm

Domaines: Informatique [cs]; Apprentissage [cs.LG]

Mostafa Haghir Chehreghani, Albert Bifet, Talel Abdessalem. Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs. PAKDD (3) 2018 : Advances in Knowledge Discovery and Data Mining: Pacific-Asia Conference on Knowledge Discovery and Data Mining, Jun 2018, Melbourne, Australia. pp.752-764, ⟨10.1007/978-3-319-93040-4_59⟩. ⟨hal-02412377⟩