Fast Truss Decomposition in Memory

The k-truss is a type of cohesive subgraphs proposed for the analysis of massive network. Existing in-memory algorithms for computing k-truss are inefficient for searching and parallel. We propose a novel traversal algorithm for truss decomposition: it effectively reduces computation complexity, we fully exploit the parallelism thanks to the optimization, and overlap IO and computation for a better performance. Our experiments on real datasets verify that it is 2x–5x faster than the exiting fastest in-memory algorithm.