Space Ecient Decremental Betweenness Algorithm for Directed Graphs

Activity: Talk or presentationTalk or presentation at a conference


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 real-world networks has shown our algorithm is faster than recalculation from scratch and competitive with recent approaches.
Period28 Jun 201930 Jun 2019
Event title2nd International Scientific Convention: Workshop 2019 on Internet of Things and Artificial Intelligence
Event typeConference
Conference number1
LocationVilla Clara, Cuba
Degree of RecognitionInternational