We present fully dynamic algorithms for maintaining betweenness centrality (BC) of vertices in a directed graph G = (V, E) with positive edge weights. BC is a widely used parameter in the analysis of large complex networks. We achieve an amortized O(v~(*2) · log~3 n) time per update with our basic algorithm, and O(v~(*2) · log~2 n) time with a more complex algorithm, where n = |V|, and v~* bounds the number of distinct edges that lie on shortest paths through any single vertex. For graphs with v~* = O(n), our algorithms match the fully dynamic all pairs shortest paths (APSP) bounds of Demetrescu and Italiano [8] and Thorup [28] for unique shortest paths, where v~* = n - 1. Our first algorithm also contains within it, a method and analysis for obtaining fully dynamic APSP from a decremental algorithm, that differs from the one in [8].
展开▼
