Geodesic
Algebraic Algorithms for Betweenness and Percolation Centrality
Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 241-261.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

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 3-tuple geodetic semiring as an extension to the usual geodetic semiring with 2-tuples [Batagelj, Journal of Mathematical Sociology, 1994]. Using the 3-tuple 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 2-tuple 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 3-tuple geodetic semiring. We used numba [Lam et al., LLVM'15, 2015] to optimize and parallelize ABC. We evaluated the performance of ABC using 2-tuple 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. 
@article{JGAA_2021_25_1_a11,
     author = {Altansuren Tumurbaatar and Matthew Sottile},
     title = {Algebraic {Algorithms} for {Betweenness} and {Percolation} {Centrality}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {241--261},
     publisher = {mathdoc},
     volume = {25},
     number = {1},
     year = {2021},
     doi = {10.7155/jgaa.00558},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00558/}
}
TY  - JOUR
AU  - Altansuren Tumurbaatar
AU  - Matthew Sottile
TI  - Algebraic Algorithms for Betweenness and Percolation Centrality
JO  - Journal of Graph Algorithms and Applications
PY  - 2021
SP  - 241
EP  - 261
VL  - 25
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00558/
DO  - 10.7155/jgaa.00558
LA  - en
ID  - JGAA_2021_25_1_a11
ER  - 
%0 Journal Article
%A Altansuren Tumurbaatar
%A Matthew Sottile
%T Algebraic Algorithms for Betweenness and Percolation Centrality
%J Journal of Graph Algorithms and Applications
%D 2021
%P 241-261
%V 25
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00558/
%R 10.7155/jgaa.00558
%G en
%F JGAA_2021_25_1_a11
Altansuren Tumurbaatar; Matthew Sottile. Algebraic Algorithms for Betweenness and Percolation Centrality. Journal of Graph Algorithms and Applications, Tome 25 (2021) no. 1, pp. 241-261. doi : 10.7155/jgaa.00558. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00558/

Cité par Sources :