# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Centrality
#### 4.1.3 Eccentricity  
**Definition 6** (**Eccentricity**[138]).: _Given a graph \(G\), the eccentricity of a vertex \(v\in V(G)\) is :_  
\[ecc(v)=\max_{u\in V(G)}dist(v,u).\]  
For the eccentricity centrality, Ref. [139] is the State-of-the-Art approach to compute eccentricity centrality for static graphs by non-trivially utilizing the upper and lower bounds of a vertex. Regarding the dynamic graphs, Ref. [48] provides the first algorithm on maintaining the eccentricities upon each edge update. It first scopes the possibly affected nodes and then facilitates a more targeted eccentricity re-computation algorithm to improve the efficiency of maintaining the eccentricities.  
**Algorithm analysis.** We analyze different centrality algorithms over various aspects including graph type, update mode and supported graph change type. As shown in Table 2, we list representative works and recent works published within the past three years. Most algorithms support fully dynamic graphs with both edge/vertex insertion/deletion. For the time complexity, Ref. [25] proposes an algorithm whose worst-time complexity is bounded by a polynomial in \(|V^{T^{\prime}}|_{i}|E^{T^{\prime}}|_{i}|V|\) and \(|E|\) where \(|V^{T^{\prime}}|\leq|V|\) and \(|E^{T^{\prime}}|\leq|E|\). In [39], \(T\) is the number of threads. \(L(B)\) denotes the set of nodes affected due to all the edges in batch \(B\)[37]. In [44], [Affected] is used to denote the sum of the number of edges and the nodes in the subgraph formed by AffectedSource and AffectedSink nodes' neighborhoods. Besides, for the complexity of closeness centrality, \(min\{|\hat{V}_{a}|,|\hat{V}_{b}|\}\) is very small in real-world networks, \(V_{\text{affect}}\) and \(E_{\text{affect}}\) are much smaller than the original graph [46; 47]. Regarding eccentricity, in [48], the empirical study indicates that the size of \(|C^{\psi}|\) is reduced to a level which is no more than \(10^{2}\), achieving high efficiency of eccentricity maintenance.  
\begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline
**Problem** & **Algorithm** & **Graph Type** & **Update Mode** & **Fully Dynamic** & **Incremental Dynamic** & **Decmental Dynamic** & **Streaming Dynamic** \\ \hline Betweenness centrality & QUB [17] & General & Single & ✓ & ✓ & ✓ & ✓ & � \\ \hline Betweenness centrality & Green [18] & General & Single & � & ✓ & � & ✓ & � \\ \hline Betweenness centrality & Lee [25] & Weighted & Batch & \(O(|V^{T}|^{2}|E^{\prime}|+|V|+|E|)\) & ✓ & ✓ & � \\ \hline Betweenness centrality & Lee [25] & General & Batch & \(O(|V^{T}|^{2}|E^{\prime}|+|V^{T}|^{2}|gg|V^{T}|+|\) & ✓ & ✓ & � \\ \hline Betweenness centrality & Green\({}^{+}\)[8] & General & Single (parallel) & ✓ & ✓ & ✓ & ✓ \\ \hline Betweenness centrality & \(i\)Central [9] & General & Single (parallel) & ✓ & \(O(|V|i|E|/T)\) & ✓ & � \\ \hline BC centrality & Shukla [7] & General & Batch (parallel) & \(O(|L|(B)|)\cdot(|V|+|E|)\) & ✓ & ✓ & � \\ \hline Closeness centrality & Kas [44] & Directed \& weighted & Single & ✓ & \(O(|\text{Affected}|)\) & \(O(|\text{Affected}|)+\) & � \\ \hline Closeness centrality & STREAMER [45] & General & Single (distributed) & ✓ & ✓ & ✓ & ✓ \\ \hline Closeness centrality & CENCY [46] & General & Single & \(O(\min(|V|_{2}|V|_{3})\cdot(|V|+|E|))\) & ✓ & ✓ & � \\ \hline Closeness centrality & ICA [67] & General & Single & \(O(|V|)\cdot O(|V_{\text{Ref.}}|)+\) & ✓ & ✓ & � \\ \hline Eccentricity & ECC-UY [68] & General & Single & \(\ ✓\) & \(O(|E|\cdot(|C|+|C^{\prime}|))\) & ✓ & � \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of time complexity for dynamic betweenness centrality algorithms.