{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T19:02:36Z","timestamp":1774983756886,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,2,10]]},"abstract":"<jats:p>\n                    Mining dense subgraphs in a bipartite graph is a fundamental task in bipartite graph analysis, with numerous applications in community detection, fraud detection, and e-commerce recommendation. Existing dense subgraph models, such as biclique,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -biplex,\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    -bitruss, and (\u03b1,\u03b2)-core, often face challenges due to their high computational complexity or limitations in effectively capturing the density of the graph. To overcome these issues, in this paper, we propose a new dense subgraph model for bipartite graphs, namely (\u03b1,\u03b2)-dense subgraph, designed to capture the density structure inherent in bipartite graphs. We show that all (\u03b1,\u03b2)-dense subgraphs are nested within each other, forming a hierarchical density decomposition of the bipartite graph. To efficiently compute the (\u03b1,\u03b2)-dense subgraph, we develop a novel network flow algorithm with a carefully-designed core pruning technique. The time complexity of our algorithm is O(|E|+|E(R)|\n                    <jats:sup>1.5<\/jats:sup>\n                    ), where |E| denotes the number of edges and |E(R)| is the number of edges of the pruned graph, often significantly smaller than |E|. Armed with this algorithm, we also propose a novel and efficient divide-and-conquer algorithm to compute the entire density decomposition of the bipartite graph within O(p \u22c5 log d\n                    <jats:sub>max<\/jats:sub>\n                    \u22c5 |E|\n                    <jats:sup>1.5<\/jats:sup>\n                    ) time, where\n                    <jats:italic toggle=\"yes\">p<\/jats:italic>\n                    is typically a small constant in real-world bipartite graphs and d\n                    <jats:sub>max<\/jats:sub>\n                    is the maximum degree. Extensive experiments and case studies on 11 real-world datasets demonstrate the effectiveness of our (\u03b1,\u03b2)-dense subgraph model and the high efficiency and scalability of our proposed algorithms.\n                  <\/jats:p>","DOI":"10.1145\/3709680","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-25","source":"Crossref","is-referenced-by-count":3,"title":["Density Decomposition of Bipartite Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-5533-3430","authenticated-orcid":false,"given":"Yalong","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0003-4496-8518","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-5841-0350","authenticated-orcid":false,"given":"Qi","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-6068-5062","authenticated-orcid":false,"given":"Lu","family":"Qin","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"ORCID":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.09.004"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37401-2_21"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687713"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824780"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008861.1008865"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Alex Beutel Wanhong Xu Venkatesan Guruswami Christopher Palow and Christos Faloutsos. 2013b. CopyCatch: stopping group attacks by spotting lockstep behavior in social networks. In WWW. 119--130.","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_8_1","unstructured":"Ivona Bez\u00e1kov\u00e1. 2000. Compact representations of graphs and adjacency testing. (2000)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Markus Blumenstock. 2016. Fast Algorithms for Pseudoarboricity. In ALENEX. 113--126.","DOI":"10.1137\/1.9781611974317.10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00505"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Lucas Augusto Montalv ao Costa Carvalho and Hendrik Teixeira Macedo. 2013. Users' satisfaction in recommendation systems for groups: an approach based on noncooperative games. In WWW. 951--958.","DOI":"10.1145\/2487788.2488090"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2015.04.001"},{"key":"e_1_2_1_13_1","volume-title":"Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024","author":"Chen Jiujian","year":"2024","unstructured":"Jiujian Chen, Kai Wang, Ronghua Li, Hongchao Qin, Xuemin Lin, and Guoren Wang. 2024. Maximal Biclique Enumeration: A Prefix Tree Based Approach. In 40th IEEE International Conference on Data Engineering, ICDE 2024, Utrecht, The Netherlands, May 13--16, 2024. IEEE, 2544--2556."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.chb.2014.12.011"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654938"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch T.-H. Hubert Chan and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming. In WWW. 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Danhao Ding Hui Li Zhipeng Huang and Nikos Mamoulis. 2017. Efficient Fault-Tolerant Group Recommendation Using alpha-beta-core. In CIKM. 2047--2050.","DOI":"10.1145\/3132847.3133130"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Jagadeesh Gorla Neal Lathia Stephen Robertson and Jun Wang. 2013. Probabilistic group recommendation via information matching. In WWW. 495--504.","DOI":"10.1145\/2488388.2488432"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.04.027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0964"},{"key":"e_1_2_1_21_1","volume-title":"Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters. In ICFCA (CEUR Workshop Proceedings","volume":"32","author":"Ignatov Dmitry I.","year":"2019","unstructured":"Dmitry I. Ignatov. 2019. Preliminary Results on Mixed Integer Programming for Searching Maximum Quasi-Bicliques and Large Dense Biclusters. In ICFCA (CEUR Workshop Proceedings, Vol. 2378). 28--32."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Boge Liu Long Yuan Xuemin Lin Lu Qin Wenjie Zhang and Jingren Zhou. 2019. Efficient (a ())-core Computation: an Index-based Approach. In WWW. 1130--1141.","DOI":"10.1145\/3308558.3313522"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/11823728_42"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69733-6_26"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3617329"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397234"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher Jakub Pachocki Richard Peng Charalampos E. Tsourakakis and Shen Chen Xu. 2015. Scalable Large Near-Clique Detection in Large-Scale Networks via Sampling. In KDD. 815--824.","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Lu Qin Rong-Hua Li Lijun Chang and Chengqi Zhang. 2015. Locally Densest Subgraph Discovery. In KDD. 965--974.","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Ahmet Erdem Sariy\u00fcce and Ali Pinar. 2018. Peeling Bipartite Networks for Dense Subgraph Discovery. In WSDM Yi Chang Chengxiang Zhai Yan Liu and Yoelle Maarek (Eds.). 504--512.","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","unstructured":"Jessica Shi and Julian Shun. 2022. Parallel Algorithms for Butterfly Computations. In Massive Graph Analytics David A. Bader (Ed.). Chapman and Hall\/CRC 287--330.","DOI":"10.1201\/9781003033707-14"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/1656479.1656483"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344210"},{"key":"e_1_2_1_33_1","volume-title":"Kai Yao, and Huynh Thi Thanh Binh.","author":"Trung Tran Ba","year":"2023","unstructured":"Tran Ba Trung, Lijun Chang, Nguyen Tien Long, Kai Yao, and Huynh Thi Thanh Binh. 2023. Verification-Free Approaches to Efficient Locally Densest Subgraph Discovery. In ICDE. 1--13."},{"key":"e_1_2_1_34_1","volume-title":"Reinders","author":"Wang Jun","year":"2006","unstructured":"Jun Wang, Arjen P. de Vries, and Marcel J. T. Reinders. 2006. Unifying user-based and item-based collaborative filtering approaches by similarity fusion. In SIGIR. 501--508."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00658-5"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-023-00786-0"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Kaiqiang Yu Cheng Long Shengxin Liu and Da Yan. 2022. Efficient Algorithms for Maximal k-Biplex Enumeration. In SIGMOD. 860--873.","DOI":"10.1145\/3514221.3517847"},{"key":"e_1_2_1_38_1","first-page":"824","article-title":"On Efficient Large Maximal Biplex Discovery","volume":"35","author":"Yu Kaiqiang","year":"2023","unstructured":"Kaiqiang Yu, Cheng Long, Deepak P, and Tanmoy Chakraborty. 2023. On Efficient Large Maximal Biplex Discovery. IEEE Trans. Knowl. Data Eng., Vol. 35, 1 (2023), 824--829.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Quan Yuan Gao Cong and Chin-Yew Lin. 2014. COM: a generative model for group recommendation. In KDD. 163--172.","DOI":"10.1145\/2623330.2623616"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-15-110"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-32049-6_14"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3709680","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3709680","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:23:11Z","timestamp":1774981391000},"score":1,"resource":{"primary":{"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3709680"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709680"],"URL":"https:\/\/summer-heart-0930.chufeiyun1688.workers.dev:443\/https\/doi.org\/10.1145\/3709680","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}