# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Cohesive Subgraph Search
#### 4.3.1 Clique Model  
**Definition 9** (Clique).: _Given a graph \(G\), a clique \(C\) is a maximal subgraph in \(G\), s.t., each pair of vertices in \(C\) are neighbors. A \(k\)-clique is a clique with \(k\) vertices._  
As illustrated in Figure 3, subgraph \(C_{1}\) is a 6-clique, while \(C_{2}\) constitutes a 5-clique.  
The clique model represents a fundamental and well-studied cohesive subgraph structure in network analysis [7]. The primary computational challenge of this model lies in exhaustively identifying all cliques within a graph \(G\) which is a task proven to be NP-hard and admits no known polynomial-time approximation algorithm [141]. Given the dynamic nature of real-world networks undergoing constant edge modifications, efficient clique maintenance algorithms have become increasingly crucial for supporting various practical applications.  
Initial research in [62] pioneered maximal clique enumeration (MCE) for dynamic graphs handling single-edge updates. Given a graph \(G\), the approach in [62] processes an edge insertion \((u,v)\) by examining all maximal cliques \(\mathcal{A}\) containing \(u\) and \(\mathcal{B}\) containing \(v\). For each pair of cliques \((A,B)\in\mathcal{A}\times\mathcal{B}\), it generates candidate cliques as \((A\cap B)\cup(u,v)\), achieving a time complexity of \(\mathrm{O}(W^{2}n^{2})\), where \(W\) represents the number of maximal cliques and \(n\) is the number of vertices. Subsequent work [65] improves this through an innovative local construction strategy using linear scans, reducing the candidate set size to \(\mathrm{O}(W)\) and overall complexity to \(\mathrm{O}(Wn^{2})\). The framework in [65] also supports edge deletion by inverting the insertion process when edges are removed.  
In addition, the research in [63] tackles the challenge of maintaining maximal cliques in dynamic graphs undergoing batch edge updates. The work makes two fundamental contributions: first, it establishes near-optimal bounds quantifying how the set of maximal cliques evolves when edges are added to the graph. Second, it introduces a novel change-sensitive algorithm for incremental clique maintenance whose computational complexity scales linearly with the actual changes in the maximal clique set--particularly effective for small edge additions. Specifically, the algorithm achieves time complexity of \(O(\Delta^{3}\rho|\Lambda^{new}(G,G^{\prime})|)\) for enumerating newly formed cliques (where \(\Delta\) represents the maximum vertex degree in the updated graph \(G^{\prime}\) and \(\rho\) denotes the number of added  
Figure 3: Example of clique.  
edges), where \(O(2^{p}|\Lambda^{new}(G,G^{\prime})|)\) is used for detecting removed cliques. Notably, the proposed method can also be applied to the decremental case. Moreover, Ref. [16] develops a parallelized version of the approach in [63], implementing a shared-memory architecture where multiple threads concurrently process clique enumeration while accessing a globally shared graph structure.  
The work in [64] investigates incremental maximal clique enumeration for dynamic graph maintenance, introducing the SOMEi data structure, a space-efficient index for storing intermediate maximal cliques during construction that enables the efficient retrieval of scope-constrained cliques.