Approximating Betweenness Centrality in Fully Dynamic Networks
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 networks that change over time. In this paper we propose the first betweenness centrality approximation algorithms with a provable guarantee on the maximum approximation error for dynamic networks. Several new intermediate algorithmic results contribute to the respective approximation algorithms: (i) new upper bounds on the vertex diameter, (ii) the first fully-dynamic algorithm for updating an approximation of the vertex diameter in undirected graphs, and (iii) an algorithm with lower time complexity for updating single-source shortest paths in unweighted graphs after a batch of edge actions. Using approximation, our algorithms are the first to make in-memory computation of betweenness in dynamic networks with millions of edges feasible. Our experiments show that our algorithms can achieve substantial speedups compared to recomputation, up to several orders of magnitude. Moreover, the approximation accuracy is usually significantly better than the theoretical guarantee in terms of absolute error. More importantly, for reasonably small approximation error thresholds, the rank of nodes is well preserved, in particular for nodes with high betweenness.
Recommendations
- Fully-dynamic approximation of betweenness centrality
- Fully dynamic betweenness centrality
- Approximating betweenness centrality in large evolving networks
- Approximating Betweenness Centrality
- Efficient algorithms for updating betweenness centrality in fully dynamic graphs
- Computing Top-k Closeness Centrality in Fully-dynamic Graphs
- scientific article; zbMATH DE number 6917138
- Community based node betweenness centrality updating algorithms in dynamic networks
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
- Approximating betweenness centrality in large evolving networks
- Better approximation of betweenness centrality
- Betweenness centrality -- incremental and faster
- CENTRALITY ESTIMATION IN LARGE NETWORKS
- Fast approximation of betweenness centrality through sampling
- Fully dynamic betweenness centrality
- Fully-dynamic approximation of betweenness centrality
- Generating Random Hyperbolic Graphs in Subquadratic Time
- scientific article; zbMATH DE number 1866312 (Why is no real title available?)
- KONECT
- On dynamic shortest paths problems
- Semidynamic algorithms for maintaining single-source shortest path trees
Cited in
(19)- Fast approximation of betweenness centrality through sampling
- Efficient algorithms for updating betweenness centrality in fully dynamic graphs
- Compressive sensing of high betweenness centrality nodes in networks
- Distance Queries in Large-Scale Fully Dynamic Complex Networks
- Fully-dynamic approximation of betweenness centrality
- Fully dynamic betweenness centrality
- Improving the betweenness centrality of a node by adding links
- scientific article; zbMATH DE number 6917138 (Why is no real title available?)
- Updating dynamic random hyperbolic graphs in sublinear time
- Rethinking centrality: the role of dynamical processes in social network analysis
- Exact and approximate algorithms for computing betweenness centrality in directed graphs
- Scalable Katz ranking computation in large static and dynamic graphs
- Approximating betweenness centrality in large evolving networks
- Computing Top-k Closeness Centrality in Fully-dynamic Graphs
- Better approximation of betweenness centrality
- A dynamical systems view of network centrality
- Approximating Betweenness Centrality
- A novel method for vertex clustering in dynamic networks
- Snapshot centrality indices in dynamic FIFO networks
This page was built for publication: Approximating Betweenness Centrality in Fully Dynamic Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5856439)
