# Recent Advances in Efficient Dynamic Graph Processing
## 4 Algorithms
### Cohesive Subgraph Search
#### 4.3.4 Truss Model  
**Definition 12 (\(k\)-truss)**. : _Given a graph \(G=(V,E)\) and an integer \(k\), a \(k\)-truss \(C\) is a maximal subgraph of \(G\), s.t., for each edge \(e=(u,v)\) in \(C\), vertex \(u\) and \(v\) form at least \(k-2\) triangles in \(G\). Further, the truss number of an edge is defined as the largest \(k\) value among all \(k\)-trusses containing this edge._  
The \(k\)-truss decomposition illustrated in Figure 6 reveals a clear structural pattern, where edges possessing higher truss numbers consistently concentrate within more densely interconnected regions of the graph. The \(k\)-truss model, originally introduced by [145], represents a significant cohesive subgraph structure with diverse applications. Given a graph \(G\), truss decomposition computes the trussness \(\tau(e)\) for each edge \(e\) in \(G\), where \(\tau(e)\) indicates the maximal \(k\)-truss containing \(e\). In dynamic settings, researchers have investigated bounded truss maintenance algorithms where for some polynomial function \(f\) and some positive integer \(c\), update cost is polynomial in \(O(f(||\text{CHANGED}||_{c}))\) with \(||\text{CHANGED}||_{c}\) is the size of \(c\)-hop neighborhood of CHANGED. Ref. [21] establishes that while edge removals permit bounded maintenance under locally persistent algorithms, edge insertions do not. The study in [82] examines truss maintenance under single-edge updates by first identifying the scope of potentially affected edges. There are two scenarios for affected edges when inserting or deleting an edge \(e_{0}\). (1) Insertion scenario--for any \(e\in E(G)\cup\{e_{0}\}\) with \(\tau(e)<\widehat{\tau(e_{0})}\), if \(e\) and \(e_{0}\) form a new triangle with weight \(\tau(e)\), or \(e\) is connected with \(e_{0}\) through a series of adjacent triangles each with weight \(\tau(e)\), then \(e\) may have \(\hat{\tau}(e)=\tau(e)+1\), where \(\hat{\tau}(e)\) denotes the new trussness of \(e\), \(\widehat{\tau(e_{0})}\) denotes the upper bound of \(\hat{\tau}(e_{0})\). (2) Deletion scenario--this is similar to the insertion scenario. Building upon the affected edge scope identification, Ref. [82] develops a update algorithm using a modified truss decomposition approach. Subsequent work in [80] extends this to vertex insertion scenarios. The State-of-the-Art [21] introduces AFF\({}^{\leq}\) as a practical bounded alternative to CHANGED for edge insertions, while maintaining removal efficiency. Their insertion algorithm achieves \(O(f(||\text{AFF}^{\leq}||_{c}))\) for some polynomial function f and some positive integer \(c\) with \(||\text{AFF}^{\leq}||_{c}\) being the size of the \(c\)-hop neighborhood of AFF\({}^{\leq}\), demonstrating up to three orders over [82] in experimental evaluations. Figure 6: Example of \(k\)-truss. While the above works focus only on single edge/vertex insertion/deletion, Ref. [77] pioneers batch processing for truss maintenance with multiple edge operations. To tackle the difficulty in quantifying the trussness changes of the edges in batch processing, The work introduces two novel metrics: sustained support and pivotal support, which can efficiently identify edges likely to change trussness, significantly narrowing the search space. Ref. [81] further investigates the truss maintenance problem and develops the superior triangle edge set concept, guaranteeing that the truss number of any affected edge changes by at most 1. The proposed parallel algorithms leverage this structure to process batch updates efficiently through iterative processing of multiple edges. Ref. [79] proposes an incremental community search solution using \(D\)-truss in dynamic directed graphs. [78] proposes truss maintenance algorithms capable of handling concurrent edge/vertex insertions and deletions in fully dynamic graphs. Compared with the approach in [77], these algorithms demonstrate superior efficiency and substantially reduce the required iteration count for processing graph updates.