K-truss decomposition for Scale-Free Graphs at Scale in Distributed Memory

We update our prior 2017 Graph Challenge submission [11] on large scale triangle counting in distributed memory by extending it to compute the full $k$ -truss decomposition [6] of large scale-free graphs. We build on heuristics to minimize ‘wedge checks', by operating on an ordered directed graph, and describe an algorithm to ‘unroll’ triangle counts when they are scheduled for pruning by the $k$ -truss decomposition. Our $k$ -truss algorithm is implemented using HavoqGT, an asynchronous vertex-centric graph analytics framework for distributed memory. We present a brief experimental evaluation on two large, real-world, scale-free graphs: a 128B edge web-graph and a 1.4B edge twitter follower graph. To our knowledge, the 128B edge web-graph is the largest real-world graph to have its $k$ -truss decomposition computed.