Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00558
Algebraic Algorithms for Betweenness and Percolation Centrality
Vol. 25, no. 1, pp. 241261, 2021. Regular paper.
Abstract In this paper, we explored different ways to write the algebraic version of betweenness centrality algorithm.
Particularly, we focused on Brandes' algorithm [Brandes, Journal of Mathematical Sociology, 2001]. We aimed for algebraic betweenness centrality that can be parallelized easily. We proposed 3tuple geodetic semiring as an extension to the usual geodetic semiring
with 2tuples [Batagelj, Journal of Mathematical Sociology, 1994]. Using the 3tuple geodetic semiring, Dijkstra's and Brandes' algorithm, we wrote more concise and general algebraic betweenness centrality (ABC) algorithm which is valid for weighted and directed graphs. We also proposed an alternative version of ABC using the usual geodetic semiring with 2tuple where we used a simple way to construct shortest path tree after computing shortest path distances in the usual geodetic semiring. This allows us to avoid computational complexity of ABC implementation using 3tuple geodetic semiring. We used numba [Lam et al., LLVM'15, 2015] to optimize and parallelize ABC. We evaluated the performance of ABC using 2tuple geodetic semiring as compared to NetworkX [Hagberg et al., SciPy 2008, 2008], a common python package for graph algorithms. We did scalability experiments on parallel ABC and showed its total speedup. We also showed that with small modification, ABC can be adapted to algebraicly compute other centrality measures such as percolation centrality.

Submitted: February 2021.
Accepted: March 2021.
Final: March 2021.
Published: April 2021.
Communicated by
Giuseppe Liotta

Journal Supporters
