EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Distributed Truss Decomposition over Large Directed Graphs

Anxin Tian, Alexander Zhou, Yue Wang, Xun Jian, Lei Chen, Yan Zhou, Chen Zhang

The VLDB Journal · 2025-09 · 34 (5)

DOI: 10.1007/s00778-025-00938-4 ↗

Kurz gefasst

Fachartikel in der Zeitschrift The VLDB Journal, online erschienen am 05.08.2025. Verfasst von Anxin Tian und 6 weiteren Autor:innen. Die Arbeit nennt 64 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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$$ k c vertices and flow triangles with at least $$k_f$$ 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}$$ DisDomConv that computes trussness pairs iteratively to a fixed point. Then, we utilize the peel idea and propose a batch-peel algorithm $$\textsf{DisBatPeel}$$ DisBatPeel , which spares the extra overhead in $$\textsf{DisDomConv}$$ 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}$$ 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}$$ StraLocPeel shows the best efficiency and scalability among all algorithms, which is on average $$42.6\times $$ 42.6 × faster than the existing sequential solution, $$27.4\times $$ 27.4 × faster than $$\textsf{DisDomConv}$$ DisDomConv , and $$12.1\times $$ 12.1 × faster than $$\textsf{DisBatPeel}$$ DisBatPeel .

Zitieren

APA

Tian, A., Zhou, A., Wang, Y., Jian, X., Chen, L., Zhou, Y., & Zhang, C. (2025). Distributed Truss Decomposition over Large Directed Graphs. The VLDB Journal, 34(5). https://doi.org/10.1007/s00778-025-00938-4

Vancouver

Tian A, Zhou A, Wang Y, Jian X, Chen L, Zhou Y, et al. Distributed Truss Decomposition over Large Directed Graphs. The VLDB Journal. 2025;34(5). doi:10.1007/s00778-025-00938-4

BibTeX
@article{Tian2025,
  author = {Tian, Anxin and Zhou, Alexander and Wang, Yue and Jian, Xun and Chen, Lei and Zhou, Yan and Zhang, Chen},
  title = {Distributed Truss Decomposition over Large Directed Graphs},
  journal = {The VLDB Journal},
  year = {2025},
  volume = {34},
  number = {5},
  doi = {10.1007/s00778-025-00938-4}
}
Kostenlos starten →