V Simposio Internacional de Estudios Humanísticos 2019

Betweenness is one of the most popular centrality measures in the analysis of social networks. Its computation has a high cost making it implausible for relatively large networks. The dynamic nature of many social networks opens up the possibility of developing faster algorithms for the dynamic version of the problem. In this work, we propose a new decremental algorithm to compute betweenness centrality of all nodes in directed graphs extracted from social networks. Our algorithm uses linear space, making it suitable for large scale applications. The experimental evaluation on a variety of networks has shown our algorithm is faster than recalculation from scratch and competitive with recent approaches.