2025/08/26 by Zhang, Yalong, Li, Rong-Hua, Zhang, Qi +1
#Databases (cs.DB) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.18616
Dense subgraph search in bipartite graphs is a fundamental problem in graph analysis, with wide-ranging applications in fraud detection, recommendation systems, and social network analysis. The recently proposed (α, β)-dense subgraph model has demonstrated superior capability in capturing the intrinsic density structure of bipartite graphs compared to existing alternatives. However, despite its modeling advantages, the (α, β)-dense subgraph model lacks efficient support for query processing and dynamic updates, limiting its practical utility in large-scale applications. To address these limitations, we propose BD-Index, a novel index that answers (α, β)-dense subgraph queries in optimal time while using only linear space O(|E|), making it well-suited for real-world applications requiring both fast query processing and low memory consumption. We further develop two complementary maintenance strategies for dynamic bipartite graphs to support efficient updates to the BD-Index. The space-efficient strategy updates the index in time complexity of O(p ⋅ |E|1.5) per edge insertion or deletion, while maintaining a low space cost of O(|E|) (the same as the index itself), where p is typically a small constant in real-world graphs. In contrast, the time-efficient strategy significantly reduces the update time to O(p ⋅ |E|) per edge update by maintaining auxiliary orientation structures, at the cost of increased memory usage up to O(p ⋅ |E|). These two strategies provide flexible trade-offs between maintenance efficiency and memory usage, enabling BD-Index to adapt to diverse application requirements. Extensive experiments on 10 large-scale real-world datasets demonstrate high efficiency and scalability of our proposed solutions.