Geodesic
An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 483-522.

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

Betweenness centrality-measuring how many shortest paths pass through a vertex-is one of the most important network analysis concepts for assessing the relative importance of a vertex. The well-known algorithm of Brandes [J. Math. Sociol. '01] computes, on an $n$-vertex and $m$-edge graph, the betweenness centrality of all vertices in $O(nm)$ worst-case time. In later work, significant empirical speedups were achieved by preprocessing degree-one vertices and by graph partitioning based on cut vertices. We contribute an algorithmic treatment of degree-two vertices, which turns out to be much richer in mathematical structure than the case of degree-one vertices. Based on these three algorithmic ingredients, we provide a strengthened worst-case running time analysis for betweenness centrality algorithms. More specifically, we prove an adaptive running time bound $O(kn)$, where $k m$ is the size of a minimum feedback edge set of the input graph.
DOI : 10.7155/jgaa.00543
Keywords: network science, social network analysis, centrality measures, shortest paths, tree-like graphs, efficient pre- and postprocessing, FPT~in~P 
@article{JGAA_2020_24_3_a16,
     author = {Matthias Bentert and Alexander Dittmann and Leon Kellerhals and Andr\'e Nichterlein and Rolf Niedermeier},
     title = {An {Adaptive} {Version} of {Brandes'} {Algorithm} for {Betweenness} {Centrality}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {483--522},
     publisher = {mathdoc},
     volume = {24},
     number = {3},
     year = {2020},
     doi = {10.7155/jgaa.00543},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00543/}
}
TY  - JOUR
AU  - Matthias Bentert
AU  - Alexander Dittmann
AU  - Leon Kellerhals
AU  - André Nichterlein
AU  - Rolf Niedermeier
TI  - An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
JO  - Journal of Graph Algorithms and Applications
PY  - 2020
SP  - 483
EP  - 522
VL  - 24
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00543/
DO  - 10.7155/jgaa.00543
LA  - en
ID  - JGAA_2020_24_3_a16
ER  - 
%0 Journal Article
%A Matthias Bentert
%A Alexander Dittmann
%A Leon Kellerhals
%A André Nichterlein
%A Rolf Niedermeier
%T An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
%J Journal of Graph Algorithms and Applications
%D 2020
%P 483-522
%V 24
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00543/
%R 10.7155/jgaa.00543
%G en
%F JGAA_2020_24_3_a16
Matthias Bentert; Alexander Dittmann; Leon Kellerhals; André Nichterlein; Rolf Niedermeier. An Adaptive Version of Brandes' Algorithm for Betweenness Centrality. Journal of Graph Algorithms and Applications, Tome 24 (2020) no. 3, pp. 483-522. doi : 10.7155/jgaa.00543. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00543/

Cité par Sources :