.png){kind=icon}
.png){kind=icon}
Return
Distributed Truss Decomposition over Large Directed Graphs
.png){kind=icon}
PRE
AI
DOI：10.1007/s00778-025-00938-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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 $$k_c$$ vertices and flow triangles with at least $$k_f$$ 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 $$\textsf{DisDomConv}$$ that computes trussness pairs iteratively to a fixed point. Then, we utilize the peel idea and propose a batch-peel algorithm $$\textsf{DisBatPeel}$$ , which spares the extra overhead in $$\textsf{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 $$\textsf{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. $$\textsf{StraLocPeel}$$ shows the best efficiency and scalability among all algorithms, which is on average $$42.6\times $$ faster than the existing sequential solution, $$27.4\times $$ faster than $$\textsf{DisDomConv}$$ , and $$12.1\times $$ faster than $$\textsf{DisBatPeel}$$ .
Keywords:
Directed graph
Cohesive subgraph discovery
Distributed graph computation
Journal
IF:
3.8
Papers:
75
Citations:
2.4K
View more organizations