Exploring Truss Maintenance in Fully Dynamic Graphs: A Mixed Structure-Based Approach
Qi Luo, Dongxiao Yu, Xiuzhen Cheng, Hao Sheng, Weifeng Lv
Abstract
Graphs are widely employed in complex system modeling, VLSI design, and social analysis. Mining cohesive subgraphs is a fundamental problem in graph analysis, while implementing cohesive subgraphs requires analysts to not only ensure cohesiveness but also consider the computational intractability. Among a variety of diverse cohesive structures, k-truss exhibits a perfect trade-off between structure tightness and computational efficiency. In a k-truss, each edge is present in at least k-2 triangles. This study aims to contribute to this growing area of truss maintenance in fully dynamic graphs by avoiding expensive re-computation. Specifically, we consider the challenging scenario of batch processing of edge and vertex insertion/deletion and propose efficient algorithms that can maintain the trusses by only searching a very small range of affected edges. Also, our algorithms allow parallel implementations to further improve the efficiency of maintenance. Extensive experiments on both real-world static and temporal graphs illustrate the efficiency and scalability of our algorithms.