Abstract. We consider the incremental computation of the betweenness centrality (BC) of all vertices in a graph G = (V, E), directed or undirected, with positive real edge-weights. The current widely used algorithm is the Brandes algorithm that runs in O(mn + n 2 log n) time, where n = |V | and m = |E|. We present an incremental algorithm that updates the BC score of all vertices in G when a new edge is added to G, or the weight of an existing edge is reduced. Our incremental algorithm runs in O(m ′ n+n 2 ) time, where m ′ is bounded by m * = |E * |, and E * is the set of edges that lie on a shortest path in G. We achieve the same bound for the more general incremental update of a vertex v, where the edge update can be performed on any subset of edges incident to v. Our incremental algorithm is the first algorithm that is asymptotically faster on sparse graphs than recomputing with the Brandes algorithm even for a single edge update. It is also likely to be much faster than the Brandes algorithm on dense graphs since m * is often close to linear in n. Our incremental algorithm is very simple, and we give an efficient cache-oblivious implementation that incurs O(scan(n 2 )+n·sort(m ′ )) cache misses, where scan and sort are well-known measures for efficient caching. We also give a static BC algorithm that runs in time O(m * n + n 2 log n), which is faster than the Brandes algorithm on any graph with m = ω(n log n) and m * = o(m). Betweenness centrality (BC) is a widely-used measure in the analysis of large complex networks. The BC of a node v in a network is the fraction of all shortest paths in the network that go through v, and this measure is often used as an index that determines the relative importance of v in the network. Some applications of BC include analyzing social interaction networks [12] , identifying lethality in biological networks [21] , and identifying key actors in terrorist networks [13, 4] . Given the changing nature of the networks under consideration, it is desirable to have algorithms that compute BC faster than computing it from scratch after every change. Our main contribution is the first incremental algorithm for computing BC after an incremental update on an edge or on a vertex that is provably faster on sparse graphs than the widely used static algorithm by Brandes [3] . By an incremental update on an edge (u, v) we mean a decrease in the weight of an existing edge (u, v), or the addition of a new edge (u, v) with finite weight if (u, v) is not present in the graph; in an incremental vertex update, updates can occur on any subset of edges incident to v, including the addition of new edges. Let G = (V, E) be a graph with positive real edge weights. Let n = |V | and m = |E|. To state our result we need the following definitions. For a vertex x ∈ V , let m * x denote the number of edges that lie on shortest paths through x. Letm * denote the average over all m * x , i.e.,m * = 1 n x∈V m * x . Finally, let m * denote the total number of edges that lie on shortest paths in G. For our incremental bound, we consider the maximum of each of these terms in the two graphs before and after the update. Here is our main result. Our method is to efficiently maintain the single source shortest paths (SSSP) directed acyclic graph (DAG) rooted at each source s ∈ V , and therefore ensure that after every change we only examine the ⋆
Nasre et al. REF present a tighter upper bound of O(nm * ) on time complexity, where m * is the number of edges that lie on shortest paths.
Betweenness Centrality -- Incremental and Faster
ArXiv
ArXiv
Computer Science Mathematics