10.3233/FI-2021-2071
Chehreghani, Mostafa Haghir
Mostafa Haghir
Chehreghani
Bifet, Albert
Albert
Bifet
Abdessalem, Talel
Talel
Abdessalem
Exact and Approximate Algorithms for Computing Betweenness Centrality in
Directed Graphs
episciences.org
2021
Computer Science - Data Structures and Algorithms
Computer Science - Social and Information Networks
contact@episciences.org
episciences.org
2021-09-06T13:51:23+02:00
2021-11-18T09:31:34+01:00
2021-11-18
eng
Journal article
https://fi.episciences.org/8451
arXiv:1708.08739
1875-8681
PDF
1
Fundamenta Informaticae ; Volume 182, Issue 3 ; 1875-8681
Graphs (networks) are an important tool to model data in different domains.
Real-world graphs are usually directed, where the edges have a direction and
they are not symmetric. Betweenness centrality is an important index widely
used to analyze networks. In this paper, first given a directed network $G$ and
a vertex $r \in V(G)$, we propose an exact algorithm to compute betweenness
score of $r$. Our algorithm pre-computes a set $\mathcal{RV}(r)$, which is used
to prune a huge amount of computations that do not contribute to the
betweenness score of $r$. Time complexity of our algorithm depends on
$|\mathcal{RV}(r)|$ and it is respectively
$\Theta(|\mathcal{RV}(r)|\cdot|E(G)|)$ and
$\Theta(|\mathcal{RV}(r)|\cdot|E(G)|+|\mathcal{RV}(r)|\cdot|V(G)|\log |V(G)|)$
for unweighted graphs and weighted graphs with positive weights.
$|\mathcal{RV}(r)|$ is bounded from above by $|V(G)|-1$ and in most cases, it
is a small constant. Then, for the cases where $\mathcal{RV}(r)$ is large, we
present a simple randomized algorithm that samples from $\mathcal{RV}(r)$ and
performs computations for only the sampled elements. We show that this
algorithm provides an $(\epsilon,\delta)$-approximation to the betweenness
score of $r$. Finally, we perform extensive experiments over several real-world
datasets from different domains for several randomly chosen vertices as well as
for the vertices with the highest betweenness scores. Our experiments reveal
that for estimating betweenness score of a single vertex, our algorithm
significantly outperforms the most efficient existing randomized algorithms, in
terms of both running time and accuracy. Our experiments also reveal that our
algorithm improves the existing algorithms when someone is interested in
computing betweenness values of the vertices in a set whose cardinality is very
small.