Finding central nodes is a fundamental problem in network analysis. Betweenness centrality is a well-known measure which quantifies the importance of a node based on the fraction of shortest paths going though it. Due to the dynamic nature of many today's networks, algorithms that quickly update centrality scores have become a necessity. For betweenness, several dynamic algorithms have been proposed over the years, targeting different update types (incremental- and decremental-only, fully-dynamic). In this paper we introduce a new dynamic algorithm for updating betweenness centrality after an edge insertion or an edge weight decrease. Our method is a combination of two independent contributions: a faster algorithm for updating pairwise distances as well as number of shortest paths, and a faster algorithm for updating dependencies. Whereas the worst-case running time of our algorithm is the same as recomputation, our techniques considerably reduce the number of operations performed by existing dynamic betweenness algorithms.
The basic idea of dynamic betweenness algorithms is to keep track of the old betweenness scores (and additional data structures) and efficiently update the information after some modification in the graph. Based on the type of updates they can handle, dynamic algorithms are classified as (only edge insertions and weight decreases), (only edge deletions and weight increases) or (all kinds of edge updates). However, one commonality of all these approaches is that they build on the techniques used by BA @cite_15 , which we therefore describe in in more detail.
@cite_15
2102347446 1992869351 2963957156 2522910400
This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of V(m0) operations, where m0 is the number of edges in the initial graph, the expected time for p updates is O( p log 3 n) (Throughout the paper the logarithms are base 2.) for connectivity and bipartiteness. The worst-case time for one query is O(log n log log n). For the k-edge witness problem ("Does the removal of k given edges disconnect the graph?") the expected time for p updates is O( p log 3 n) and the expected time for q queries is O(qk log 3 n). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O( pk log 3 n). This implies an algorithm to maintain a 1 1 e-approximation of the minimum spanning tree in expected time O((p log 3 n log U) e) for p updates, where the weights of the edges are between 1 and U. This paper solves a longstanding open problem in fully dynamic algorithms: We present the first fully dynamic algorithms that maintain connectivity, bipartiteness, and approximate minimum spanning trees in polylogarithmic time per edge insertion or deletion. The algorithms are designed using a new dynamic technique that combines a novel graph decomposition with randomization. They are Las-Vegas type randomized algorithms which use simple data structures and have a small constant factor. Let n denote the number of nodes in the graph. For a sequence of O( m 0 ) operations, where m 0 is the number of edges in the initial graph, the expected time for p updates is O ( p log 3 n ) (througout the paper the logarithms are based 2) for connectivity and bipartiteness. The worst-case time for one query is O (log n log log n ). For the k -edge witness problem (“Does the removal of k given edges disconnect the graph?”) the expected time for p updates is O ( p log 3 n ) and the expected time for q queries is O ( qk log 3 n ). Given a graph with k different weights, the minimum spanning tree can be maintained during a sequence of p updates in expected time O ( pk log 3 n ). This implies an algorithm to maintain a 1 + e-approximation of the minimum spanning tree in expected time O (( p log 3 n log U ) e) for p updates, where the weights of the edges are between 1 and U . Betweenness centrality ranks the importance of nodes by their participation in all shortest paths of the network. Therefore computing exact betweenness values is impractical in large networks. For static networks, approximation based on randomly sampled paths has been shown to be significantly faster in practice. However, for dynamic networks, no approximation algorithm for betweenness centrality is known that improves on static recomputation. We address this deficit by proposing two incremental approximation algorithms (for weighted and unweighted connected graphs) which provide a provable guarantee on the absolute approximation error. Processing batches of edge insertions, our algorithms yield significant speedups up to a factor of 104 compared to restarting the approximation. This is enabled by investing memory to store and efficiently update shortest paths. As a building block, we also propose an asymptotically faster algorithm for updating the SSSP problem in unweighted graphs. Our experimental study shows that our algorithms are the first to make in-memory computation of a betweenness ranking practical for million-edge semi-dynamic networks. Moreover, our results show that the accuracy is even better than the theoretical guarantees in terms of absolute errors and the rank of nodes is well preserved, in particular for those with high betweenness. Dynamic connectivity is one of the most fundamental problems in dynamic graph algorithms. We present a new randomized dynamic connectivity structure with @math amortized expected update time and @math query time, which comes within an @math factor of a lower bound due to and Demaine. The new structure is based on a dynamic connectivity algorithm proposed by Thorup in an extended abstract at STOC 2000, which left out some important details.