@inproceedings{94d8e8668a834117a8bee568e2a5200e,
title = "Efficient exact and approximate algorithms for computing betweenness centrality in directed graphs",
abstract = "In this paper, first given a directed network G and a vertex r∈ 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 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.",
keywords = "Approximate algorithm, Betweenness centrality, Directed graphs, Exact algorithm",
author = "Chehreghani, \{Mostafa Haghir\} and Albert Bifet and Talel Abdessalem",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 22nd Pacific-Asia Conference on Advances in Knowledge Discovery and Data Mining, PAKDD 2018 ; Conference date: 03-06-2018 Through 06-06-2018",
year = "2018",
month = jan,
day = "1",
doi = "10.1007/978-3-319-93040-4\_59",
language = "English",
isbn = "9783319930398",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "752--764",
editor = "Webb, \{Geoffrey I.\} and Dinh Phung and Mohadeseh Ganji and Lida Rashidi and Tseng, \{Vincent S.\} and Bao Ho",
booktitle = "Advances in Knowledge Discovery and Data Mining - 22nd Pacific-Asia Conference, PAKDD 2018, Proceedings",
}