Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs

The (α, β)-core, a.k.a. bi-core, is a fundamental model in bipartite graphs, extensively applied in various real-world applications such as product recommendation, fraud detection, and community detection. The dynamic nature of bipartite graphs, with frequent insertions and deletions of vertices and edges, makes maintaining bi-cores computationally expensive. Although recent work has addressed bi-core maintenance in dynamic bipartite graphs, existing approaches lack theoretical analysis regarding the changes in bi-cores corresponding to graph modifications, and also struggle with scalability and frequency of updates. To tackle these challenges, we systematically analyze and present bi-core maintenance algorithms with theoretical guarantees. Specifically, we conduct boundedness analysis, a key tool for analyzing incremental algorithms over dynamic graphs, on the bi-core maintenance problem. Our theoretical analysis shows that while the bi-core maintenance problem stays bounded under edge deletions, it becomes unbounded when handling edge insertions. To handle this unboundedness, we propose a novel structure called the BD-Order, which transforms the solution into a near bounded one. By leveraging the BD-Order, we introduce a novel order-based maintenance algorithm that effectively reduces the scope of affected vertices, thus enhancing efficiency. Additionally, the algorithm remains bounded for edge deletions through an auxiliary structure. The comprehensive experimental results on diverse real and synthetic datasets underscore the superior performance of our algorithms. Particularly, they achieve speed enhancements of up to two orders of magnitude over the state-of-the-art approaches.