Fully-Dynamic Approximation of Betweenness Centrality

DOI10.1007/978-3-662-48350-3_14zbMath1465.68204arXiv1504.07091OpenAlexW2133503202MaRDI QIDQ3452779

Elisabetta Bergamini, Henning Meyerhenke

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1504.07091

zbMATH Keywords

shortest pathsapproximation algorithmsbetweenness centralityalgorithmic network analysisfully-dynamic graph algorithms

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Fully-Dynamic Approximation of Betweenness Centrality ⋮ KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation ⋮ Fast approximation of betweenness centrality through sampling ⋮ Approximating Betweenness Centrality in Fully Dynamic Networks

Uses Software

• KONECT
• NetworKit

Cites Work

• On dynamic shortest paths problems
• Semidynamic algorithms for maintaining single-source shortest path trees
• A faster algorithm for betweenness centrality*
• Betweenness Centrality – Incremental and Faster
• A Faster Algorithm to Update Betweenness Centrality after Node Alteration
• Fully-Dynamic Approximation of Betweenness Centrality
• Generating Random Hyperbolic Graphs in Subquadratic Time
• An Incremental Algorithm for a Generalization of the Shortest-Path Problem
• Approximating Betweenness Centrality
• CENTRALITY ESTIMATION IN LARGE NETWORKS

This page was built for publication: Fully-Dynamic Approximation of Betweenness Centrality