Bitruss Maintenance on Dynamic Bipartite Graphs
Open Access
- 14 November 2026
- journal article
- research article
- Published by MDPI AG in Electronics
- Vol. 15 (22) , 5300
Abstract
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 for insertion and 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.
Keywords
Funding Information
- National Natural Science Foundation of China (62372101)