A Novel Parallel Approach With Index Optimization for Truss Maintenance

Abstract

The <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="bai-ieq1-3702362.gif"/></alternatives></inline-formula>-truss is a type of cohesive subgraph where each edge is contained in at least <inline-formula><tex-math notation="LaTeX">$k-2$</tex-math><alternatives><mml:math><mml:mrow><mml:mi>k</mml:mi><mml:mo>-</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:math><inline-graphic xlink:href="bai-ieq2-3702362.gif"/></alternatives></inline-formula> triangles within the subgraph, and it is commonly used in community search and dense subgraph discovery. Although <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="bai-ieq3-3702362.gif"/></alternatives></inline-formula>-trusses can be computed in polynomial time, obtaining all <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="bai-ieq4-3702362.gif"/></alternatives></inline-formula>-trusses of a dynamic graph that evolves over time through edge insertions and deletions remains computationally expensive. To address this challenge, prior studies proposed truss maintenance approaches that update the affected <inline-formula><tex-math notation="LaTeX">$k$</tex-math><alternatives><mml:math><mml:mi>k</mml:mi></mml:math><inline-graphic xlink:href="bai-ieq5-3702362.gif"/></alternatives></inline-formula>-trusses when the dynamic graph changes. However, existing approaches only utilize one tool of parallelism or auxiliary indexes due to latent conflicts, which restricts their overall performance. To resolve this limitation, we propose a novel parallel approach with index optimization that effectively resolves the conflicts between parallelism and index maintenance. Specifically, we first establish a novel truss maintenance theory based on auxiliary indexes, which ensures the feasibility and correctness of our maintenance solution. Second, we design two effective edge partitioning strategies to improve the parallelism of the proposed algorithms. Finally, we implement two efficient parallel algorithms that cooperate with auxiliary indexes to reduce maintenance costs. Extensive experiments on real-world graphs demonstrate that our methods outperform all baseline approaches by up to one order of magnitude.