Fully-dynamic approximation of betweenness centrality
From MaRDI portal
Abstract: Betweenness is a well-known centrality measure that ranks the nodes of a network according to their participation in shortest paths. Since an exact computation is prohibitive in large networks, several approximation algorithms have been proposed. Besides that, recent years have seen the publication of dynamic algorithms for efficient recomputation of betweenness in evolving networks. In previous work we proposed the first semi-dynamic algorithms that recompute an approximation of betweenness in connected graphs after batches of edge insertions. In this paper we propose the first fully-dynamic approximation algorithms (for weighted and unweighted undirected graphs that need not to be connected) with a provable guarantee on the maximum approximation error. The transfer to fully-dynamic and disconnected graphs implies additional algorithmic problems that could be of independent interest. In particular, we propose a new upper bound on the vertex diameter for weighted undirected graphs. For both weighted and unweighted graphs, we also propose the first fully-dynamic algorithms that keep track of such upper bound. In addition, we extend our former algorithm for semi-dynamic BFS to batches of both edge insertions and deletions. Using approximation, our algorithms are the first to make in-memory computation of betweenness in fully-dynamic networks with millions of edges feasible. Our experiments show that they can achieve substantial speedups compared to recomputation, up to several orders of magnitude.
Recommendations
Cites work
- A faster algorithm for betweenness centrality*
- A Faster Algorithm to Update Betweenness Centrality after Node Alteration
- An Incremental Algorithm for a Generalization of the Shortest-Path Problem
- Approximating Betweenness Centrality
- Betweenness centrality -- incremental and faster
- CENTRALITY ESTIMATION IN LARGE NETWORKS
- Fully-dynamic approximation of betweenness centrality
- Generating Random Hyperbolic Graphs in Subquadratic Time
- On dynamic shortest paths problems
- Semidynamic algorithms for maintaining single-source shortest path trees
Cited in
(14)- Fast approximation of betweenness centrality through sampling
- Efficient algorithms for updating betweenness centrality in fully dynamic graphs
- Distance Queries in Large-Scale Fully Dynamic Complex Networks
- Decremental All-Pairs ALL Shortest Paths and Betweenness Centrality
- Fully-dynamic approximation of betweenness centrality
- Fully dynamic betweenness centrality
- scientific article; zbMATH DE number 6917138 (Why is no real title available?)
- KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
- An Adaptive Version of Brandes' Algorithm for Betweenness Centrality
- Approximating betweenness centrality in large evolving networks
- Computing Top-k Closeness Centrality in Fully-dynamic Graphs
- Better approximation of betweenness centrality
- Approximating Betweenness Centrality
- Approximating Betweenness Centrality in Fully Dynamic Networks
This page was built for publication: Fully-dynamic approximation of betweenness centrality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452779)
