EUVIMEDEUVIMED entdecken
Crossref

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

Qiaoyuan Yang, Wensheng Luo, Yixiang Fang, Yuanyuan Zeng

Proceedings of the ACM on Management of Data · 02.04.2026 · 4 (1) · 1-26

DOI: 10.1145/3786674 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 07.04.2026. Verfasst von Qiaoyuan Yang und 3 weiteren Autor:innen. Die Arbeit nennt 58 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Yang, Q., Luo, W., Fang, Y., & Zeng, Y. (2026). Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs. Proceedings of the ACM on Management of Data, 4(1), 1-26. https://doi.org/10.1145/3786674

Vancouver

Yang Q, Luo W, Fang Y, Zeng Y. Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs. Proceedings of the ACM on Management of Data. 2026;4(1):1-26. doi:10.1145/3786674

BibTeX
@article{Yang2026,
  author = {Yang, Qiaoyuan and Luo, Wensheng and Fang, Yixiang and Zeng, Yuanyuan},
  title = {Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs},
  journal = {Proceedings of the ACM on Management of Data},
  year = {2026},
  volume = {4},
  number = {1},
  pages = {1--26},
  doi = {10.1145/3786674}
}
Kostenlos starten →