Space Efficient Incremental Betweenness Algorithm for Directed Graphs

Abstract

Betweenness is one of the most popular centrality measures in the analysis of social networks. Its computation has a high computational 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 incremental algorithm to compute the betweenness centrality of all nodes in directed graphs extracted from social networks. The algorithm uses linear space, making it suitable for large scale applications. Our experimental evaluation on a variety of real-world networks have shown our algorithm is faster than recalculation from scratch and competitive with recent approaches.

Publication
Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications