Bitruss Maintenance on Dynamic Bipartite Graphs
Electronics · 14.11.2026 · 15 (22) · 5300
DOI: 10.3390/electronics15225300 ↗Kurz gefasst
Fachartikel in der Zeitschrift Electronics, online erschienen am 14.11.2026. Verfasst von Jing Bai und 3 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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.
Förderung
- National Natural Science Foundation of China
Zitieren
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}
}
EUVIMED