  Betweenness centrality ranks the importance of nodes by their participation
in all shortest paths of the network. Therefore computing exact betweenness
values is impractical in large networks. For static networks, approximation
based on randomly sampled paths has been shown to be significantly faster in
practice. However, for dynamic networks, no approximation algorithm for
betweenness centrality is known that improves on static recomputation. We
address this deficit by proposing two incremental approximation algorithms (for
weighted and unweighted connected graphs) which provide a provable guarantee on
the absolute approximation error. Processing batches of edge insertions, our
algorithms yield significant speedups up to a factor of $10^4$ compared to
restarting the approximation. This is enabled by investing memory to store and
efficiently update shortest paths. As a building block, we also propose an
asymptotically faster algorithm for updating the SSSP problem in unweighted
graphs. Our experimental study shows that our algorithms are the first to make
in-memory computation of a betweenness ranking practical for million-edge
semi-dynamic networks. Moreover, our results show that the accuracy is even
better than the theoretical guarantees in terms of absolutes errors and the
rank of nodes is well preserved, in particular for those with high betweenness.
