Distributed Truss Decomposition over Large Directed Graphs

To capture vertex relationships in graphs, triangles are used since they represent the minimal structural unit that provides both closure and path redundancy. In directed graphs, triangles can be divided into cycle triangles and flow triangles. A D-truss is a subgraph that requires each edge forms cycle triangles with at least kc vertices and flow triangles with at least kf vertices. Though the D-truss decomposition is effective for revealing the cycle-flow relationships in directed graphs, its single-machine solutions are far from scalable for real-world large graphs. In this work, we propose efficient distributed solutions for D-truss decomposition. First, we introduce a converge-based algorithm DisDomConv that computes trussness pairs iteratively to a fixed point. Then, we utilize the peel idea and propose a batch-peel algorithm DisBatPeel, which spares the extra overhead in DisDomConv. For addressing the bottleneck of communication cost, we propose triangle-related acceleration and the type-aware balanced partitioner. Finally, we present the stratified local-peel method StraLocPeel that reduces considerable communication overhead. The experiments on real-world graphs verify that all of our solutions solve D-truss decomposition on large real-world graphs within limited time. StraLocPeel shows the best efficiency and scalability among all algorithms, which is on average 42.6× faster than the existing sequential solution, 27.4× faster than DisDomConv, and 12.1× faster than DisBatPeel.