EUVIMEDOpdag EUVIMED
Open access · CC BY 4.0

Bitruss Maintenance on Dynamic Bipartite Graphs

Jing Bai, Junfeng Zhou, Ming Du, Ziyang Chen

Electronics · 2026-11-14 · 15 (22) · 5300

DOI: 10.3390/electronics15225300 ↗

At a glance

Journal article in Electronics, published online on 2026-11-14. Written by Jing Bai and 3 co-authors. The full text is freely available (open access, CC BY 4.0). Funded by: National Natural Science Foundation of China.

AbstractBibliografiske oplysningerCiteRelated studies

Abstract (original language)

Bitruss maintenance updates the hierarchy of cohesive subgraphs in a bipartite graph as edges are inserted or deleted. Existing support-driven methods repeatedly search the graph for butterflies during candidate expansion and support recomputation. We propose an index-based approach that maintains butterfly associations in a compressed bloom-edge index. By fixing the vertex priority order, we preserve the assignment of surviving butterflies and update only the affected blooms. On this index, we develop four successive algorithms. BM performs level-by-level maintenance; SA shares qualified-path counts and aggregates support losses; SAP reduces candidate expansion through structural filters and early eviction; and SAP+ maintains exact own-level support across updates. We prove correctness for both insertion and deletion using candidate coverage, threshold peeling, and support invariants. Experiments on nine real-world bipartite graphs evaluate independent single-edge updates that create or destroy butterflies. Relative to the single-threaded PI*/PR* baselines on matching workloads, SAP+ achieves geometric mean speedups of 50.44× for insertion and 114.56× for deletion. Further experiments evaluate each refinement and verify exact maintenance with an index size close to fresh rebuilding over the evaluated accumulating-update sequences.

Funding

  • National Natural Science Foundation of China

Cite

APA

Bai, J., Zhou, J., Du, M., & Chen, Z. (2026). Bitruss Maintenance on Dynamic Bipartite Graphs. Electronics, 15(22), 5300. https://doi.org/10.3390/electronics15225300

Vancouver

Bai J, Zhou J, Du M, Chen Z. Bitruss Maintenance on Dynamic Bipartite Graphs. Electronics. 2026;15(22):5300. doi:10.3390/electronics15225300

BibTeX
@article{Bai2026,
  author = {Bai, Jing and Zhou, Junfeng and Du, Ming and Chen, Ziyang},
  title = {Bitruss Maintenance on Dynamic Bipartite Graphs},
  journal = {Electronics},
  year = {2026},
  volume = {15},
  number = {22},
  pages = {5300},
  doi = {10.3390/electronics15225300}
}
Start for free →