LEE, Min-Joong, CHOI, Sunghee and CHUNG, Chin-Wan, 2016. Efficient algorithms for updating betweenness centrality in fully dynamic graphs. Information Sciences. 2016. Vol. 326, p. 278–296. pdf 
Betweenness centrality of a vertex (edge) in a graph is a measure for the relative participation of the vertex (edge) in the shortest paths in the graph. Betweenness centrality is widely used in various areas such as biology, transportation, and social networks. In this paper, we study the update problem of betweenness centrality in fully dynamic graphs. The proposed update algorithm substantially reduces the number of shortest paths which should be re-computed when a graph is changed. In addition, we adapt a community detection algorithm using the proposed algorithm to show how much benefit can be obtained from the proposed algorithm in a practical application. Experimental results on real graphs show that the proposed algorithm efficiently update betweenness centrality and detect communities in a graph.
[…] Consider an Edge Insertion example in Fig. 1.
Fig. 1. Graph update example (numbers are edge weights).
[…] We want to figure out which shortest paths are changed due to the insertion of edge e(v6, v8). Let G be the original graph and G^U be the updated graph of G. It is trivial to see that the shortest path between v6 and v8 is changed. In addition, the shortest paths, which include the original shortest path between v6 and v8, are changed (e.g., the shortest path between v5 and v8). Let us assume that we have an index structure which stores all the shortest paths in the graph. Then we may easily identify such shortest paths. However, some shortest paths in the graph are changed although they did not include the original shortest path between v6 and v8. The shortest path between v1 and v11 in G did not include the former shortest path between v6 and v8, but it is changed to include the inserted edge e(v6, v8). Such shortest paths cannot be easily identified even if we store all the shortest paths in a graph in an index.