{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T21:05:29Z","timestamp":1775595929997,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,4,2]]},"abstract":"<jats:p>The (\u03b1, \u03b2)-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.<\/jats:p>","DOI":"10.1145\/3786674","type":"journal-article","created":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T17:54:13Z","timestamp":1775584453000},"page":"1-26","source":"Crossref","is-referenced-by-count":0,"title":["Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-8024-8411","authenticated-orcid":false,"given":"Qiaoyuan","family":"Yang","sequence":"first","affiliation":[{"name":"School of Computer Science, Peking University, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1463-814X","authenticated-orcid":false,"given":"Wensheng","family":"Luo","sequence":"additional","affiliation":[{"name":"College of Computer Science and Electronic Engineering, Hunan University, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3764-6476","authenticated-orcid":false,"given":"Yuanyuan","family":"Zeng","sequence":"additional","affiliation":[{"name":"School of Data Science, The Chinese University of Hong Kong, Shenzhen, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,4,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/APVIS.2007.329304"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2013.2297918"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37401-2_21"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/320176.320180"},{"key":"e_1_2_1_5_1","volume-title":"Generalized core maintenance of dynamic bipartite graphs. Data Mining and Knowledge Discovery","author":"Bai Wen","year":"2022","unstructured":"Wen Bai, Yadi Chen, Di Wu, Zhichuan Huang, Yipeng Zhou, and Chuan Xu. 2022. Generalized core maintenance of dynamic bipartite graphs. Data Mining and Knowledge Discovery (2022), 1-31."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45749-6_17"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.06.052"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.2982878"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2882837"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544-3550","author":"Chen Yankai","year":"2021","unstructured":"Yankai Chen, Jie Zhang, Yixiang Fang, Xin Cao, and Irwin King. 2021. Efficient community search over large directed graphs: An augmented index-based approach. In Proceedings of the Twenty-Ninth International Conference on International Joint Conferences on Artificial Intelligence (IJCAI). 3544-3550."},{"key":"e_1_2_1_13_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report, Vol. 16, 3.1 (2008), 1-29."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00540-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28434"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3133130"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035944"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3500930"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2489791"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.70"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3605573.3605597"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977578.ch2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2010.07.007"},{"key":"e_1_2_1_28_1","volume-title":"Jeffrey Xu Yu, and Rui Mao","author":"Li Rong-Hua","year":"2013","unstructured":"Rong-Hua Li, Jeffrey Xu Yu, and Rui Mao. 2013. Efficient core maintenance in large dynamic graphs. IEEE transactions on knowledge and data engineering, Vol. 26, 10 (2013), 2453-2465."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-020-00606-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3490148.3538569"},{"key":"e_1_2_1_32_1","volume-title":"Modeling protein interacting groups by quasi-bicliques: complexity, algorithm, and application","author":"Liu Xiaowen","year":"2008","unstructured":"Xiaowen Liu, Jinyan Li, and Lusheng Wang. 2008. Modeling protein interacting groups by quasi-bicliques: complexity, algorithm, and application. IEEE\/ACM transactions on computational biology and bioinformatics, Vol. 7, 2 (2008), 354-364."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00072"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617329"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11280-021-00927-x"},{"key":"e_1_2_1_37_1","first-page":"729","article-title":"Strength Lies in Differences'' Diversifying Friends for Recommendations through Subspace Clustering","author":"Ntoutsi Eirini","year":"2014","unstructured":"Eirini Ntoutsi, Kostas Stefanidis, Katharina Rausch, and Hans-Peter Kriegel. 2014. '' Strength Lies in Differences'' Diversifying Friends for Recommendations through Subspace Clustering. In CIKM. 729-738.","journal-title":"CIKM."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00079-8"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536344"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0423-8"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_42_1","volume-title":"Network structure and minimum degree. Social networks","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman. 1983. Network structure and minimum degree. Social networks, Vol. 5, 3 (1983), 269-287."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.53"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589278"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.05.004"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3481963"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00217"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00015"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498235"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570701"},{"key":"e_1_2_1_52_1","unstructured":"Qiaoyuan Yang Wensheng Luo Yixiang Fang and Yuanyuan Zeng. 2026. Order-based Algorithms for Efficient Core Maintenance in Large Bipartite Graphs (full paper). (2026). https:\/\/github.com\/QuanQuan0\/Bicore-Maintenance-Order-Full-Paper\/blob\/main\/full_paper.pdf"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3726302.3730263"},{"key":"e_1_2_1_54_1","volume-title":"On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics","author":"Zhang Yun","year":"2014","unstructured":"Yun Zhang, Charles A Phillips, Gary L Rogers, Erich J Baker, Elissa J Chesler, and Michael A Langston. 2014. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics, Vol. 15 (2014), 1-18."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3300082"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.93"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3677129"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3769785"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3786674","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T20:01:35Z","timestamp":1775592095000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3786674"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,2]]},"references-count":58,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,4,2]]}},"alternative-id":["10.1145\/3786674"],"URL":"https:\/\/doi.org\/10.1145\/3786674","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,2]]}}}