# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Cohesive Subgraph Search
#### 4.3.3 Core Model  
**Definition 11** (\(k\)-core). : _Given a graph \(G\) and an integer \(k\), a \(k\)-core is a maximal subgraph in \(G\), s.t., the degree of each vertex \(v\) in it is not less than \(k\)._  
As illustrated in Figure 5, the graph exhibits a hierarchical \(k\)-core structure comprising 1-core, 2-core, and 3-core layers. The visualization employs progressively darker shading for vertices with higher core numbers, which effectively demonstrates the nested nature of the \(k\)-core decomposition model. The core maintenance problem in dynamic graphs involves efficiently updating vertex core numbers after the insertion/deletion of vertices/edges. Modern distributed computing platforms have inspired various parallel approaches for \(k\)-core index construction and maintenance, designed to maximize resource utilization through scalable distributed architectures [68]. Specifically, Ref. [73] investigates distributed core maintenance under multi-edge updates, demonstrating that only a constant number of vertices require core number reevaluation when the original graph is updated through single or multiple edge insertions/deletions. \begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline
**Problem** & **Algorithm** & **Graph Type** & **Update Mode** & \begin{tabular}{c} **Fully** \\ **Dynamic** \\ \end{tabular} & \begin{tabular}{c} **Incremental Dynamic** \\ \end{tabular} & \begin{tabular}{c} **Decmental** \\ **Dynamic** \\ \end{tabular} & \
\begin{tabular}{c} **Streaming** \\ **Dynamic** \\ \end{tabular} \\ \hline MCE & Stix [62] & General & Batch & \(O(W^{2}n^{2})\) & ✓ & ✓ & ✗ \\ \hline MCE & Sun [65] & General & Single & ✗ & \(O(Wn^{2})\) & \(O(Wn^{2})\) & ✗ \\ \hline MCE & Das [63] & General & Batch & ✗ & \(O(\Delta^{3}\rho|\Lambda^{new}|)\) & ✓ & ✗ \\ \hline MCE & SOMEi [64] & General & Batch & ✓ & ✓ & ✓ & ✗ \\ \hline MCE & ParIMCE [16] & General &
\begin{tabular}{c} Batch \\ (parallel) \\ \end{tabular} & ✗ & ✓ & ✗ & ✗ \\ \hline MBE & DynamicBC [66] & Bipartited & Batch & ✗ & \(O(\Delta^{2}\rho|\Lambda^{new}|+2^{\rho}|\Lambda^{new}|)\) & ✗ & ✗ \\ \hline MBE & IMBS [67] & Bipartited & Single & ✗ & ✓ & ✗ & ✗ \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Comparison of time complexity for dynamic clique and biclique algorithms. Figure 5: Example of \(k\)-core. In addition, parallel computing approaches have emerged as powerful solutions for core maintenance, leveraging multi-threading and shared-memory architectures to boost performance. Ref. [69] is a pioneering work in this direction with its joint edge set structure and corresponding parallel algorithms. Subsequent work [71; 72] develops parallel methods for batch edge processing, establishing the important theoretical result that each edge operation affects vertex core numbers by at most 1. Notably, Ref. [72] proves that edge changes forming a matching can be processed in parallel. Meanwhile, Ref. [19] takes a hierarchical perspective, analyzing the structural properties of \(k\)-core hierarchies in dynamic graphs and developing efficient local update strategies for edge modifications. Building upon the superior edge set framework, Ref. [20] develops unified algorithms for incremental and decremental core maintenance for batch edge operations. These algorithms enable parallel execution by distributing edges sharing common core numbers across threads. Subsequent work in [75] enhances parallelism through the theory of \(k\)-insertion/removal graph. While traditional parallel approaches relying on traversal algorithms face sequential bottlenecks when processing uniform-core graphs, Ref. [76] overcomes this limitation by adapting the order algorithm to maintain parallelism regardless of core number distribution. **Algorithm analysis. ** We compare difference core maintenance algorithms over dynamic graph. As shown in Table 5, all core maintenance algorithms support fully dynamic graphs. Existing works have explored a variety of efficient approaches, including single-threaded, parallel, and distributed methods.