EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Bitruss Maintenance on Dynamic Bipartite Graphs

Jing Bai, Junfeng Zhou, Ming Du, Ziyang Chen

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →