Parallel Truss Maintenance of Dynamic Graphs
Longzhi Li, Yuncheng Jiang · 2023
Cohesive subgraphs have been a hot research topic in graph data mining, where k-truss is a well-established metric for describing the density of graphs. The k-truss of a graph is the largest subgraph, in which each edge is contained in at least k − 2 triangles. For large-scale dynamic graphs with a few edge changes, truss decomposition takes a high cost to recalculate the truss number of edges, where the truss number indicates the densest k-truss that one edge can be located. Instead, truss maintenance algorithms can directly update the truss number of affected edges and thus decrease the cost. However, previous maintenance algorithms usually suffer from high traversal costs and poor parallelism. We further investigate the truss maintenance problem and propose the superior triangle edge set, which increases/decreases the truss numbers of affected edges by at most 1. Meanwhile, the superior triangle edge set can improve the parallelism of the proposed algorithms. Extensive experiments on real-world graphs of different scales show that our algorithms exhibit good performance and parallelism, and their efficiency outperforms state-of-the-art algorithms by at most one order of magnitude.