Title: Efficient Exact and Approximate Algorithms for Computing Betweenness Centrality in Directed Graphs,
Abstract: Graphs are an important tool to model data in different domains, including
social networks, bioinformatics and the world wide web. Most of the networks
formed in these domains are directed graphs, where all 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 a new 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 in the betweenness score of $r$. Time complexity of our exact
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 of 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 in most cases, our algorithm significantly outperforms the most efficient
existing randomized algorithms, in terms of both running time and accuracy. Our
experiments also show that our proposed algorithm computes betweenness scores
of all vertices in the sets of sizes 5, 10 and 15, much faster and more
accurate than the most efficient existing algorithms.