A Two-stage Algorithm Based on Prediction and Search for Maxk-Truss Decomposition

The cohesive subgraph K-truss is often used to detect communities in large-scale social networks. The truss decomposition algorithm calculates the number of triangles formed by each edge, then peels off the edges with the number of triangles less than k-2 iteratively. The incremental maxk-truss algorithm must detect k-truss one by one making it inefficient. We propose a two-stage maxk-ktruss decomposition algorithm PSKT. The innovation points of PSKT are as follows: 1) The k-core structure is used to predict the maxk value, and the structure helps us avoid unnecessary mass calculations. 2) The characteristic that the k-truss of graph G must be included in the (k-1)-core of graph G is utilized to ensure that the proposed algorithm can safely prune in the graph. 3) A suitable triangle counting algorithm and the dynamic stream compression method are used to improve the algorithm efficiency. Comprehensive experiments demonstrate that PSKT is 15.26 times faster than the incremental algorithm FMT-dec and 3 times faster than the state-of-the-art maxk-truss algorithm FMT-max.