{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:44:34Z","timestamp":1788482674773,"version":"build-2803163510"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T00:00:00Z","timestamp":1686614400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Basic and Applied Basic Research Fund in Guangdong Province","award":["2022A1515010166; 2023A1515011280"],"award-info":[{"award-number":["2022A1515010166; 2023A1515011280"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC","doi-asserted-by":"crossref","award":["62102341"],"award-info":[{"award-number":["62102341"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Shenzhen Science and Technology Program","award":["JCYJ20220530143602006; ZDSYS20211021111415025"],"award-info":[{"award-number":["JCYJ20220530143602006; ZDSYS20211021111415025"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,6,13]]},"abstract":"<jats:p>The densest subgraph problem (DSP) is of great significance due to its wide applications in different domains. Meanwhile, diverse requirements in various applications lead to different density variants for DSP. Unfortunately, existing DSP algorithms cannot be easily extended to handle those variants efficiently and accurately. To fill this gap, we first unify different density metrics into a generalized density definition. We further propose a new model, c-core, to locate the general densest subgraph and show its advantage in accelerating the searching process. Extensive experiments show that our c-core-based optimization can provide up to three orders of magnitude speedup over baselines. Moreover, we study an important variant of DSP under a size constraint, namely the densest-at-least-k-subgraph (DalkS) problem. We propose an algorithm based on graph decomposition, and it is likely to give a solution that is at least 0.8 of the optimal density in our experiments, while the state-of-the-art method can only ensure a solution with density at least 0.5 of the optimal density. Our experiments show that our DalkS algorithm can achieve at least 0.99 of the optimal density for over one-third of all possible size constraints.<\/jats:p>","DOI":"10.1145\/3589314","type":"journal-article","created":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T20:26:45Z","timestamp":1687292805000},"page":"1-27","source":"Crossref","is-referenced-by-count":19,"title":["Efficient and Effective Algorithms for Generalized Densest Subgraph Discovery"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-2129-1331","authenticated-orcid":false,"given":"Yichen","family":"Xu","sequence":"first","affiliation":[{"name":"Chinese University of HongKong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3243-8512","authenticated-orcid":false,"given":"Chenhao","family":"Ma","sequence":"additional","affiliation":[{"name":"Chinese University of HongKong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5047-8593","authenticated-orcid":false,"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"Chinese University of HongKong, Shenzhen, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2477-381X","authenticated-orcid":false,"given":"Zhifeng","family":"Bao","sequence":"additional","affiliation":[{"name":"RMIT University, Melbourne, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_2_2_1_1","series-title":"SIAM J. Comput","volume-title":"Improved Algorithms for Bipartite Network Flow","author":"Ahuja Ravindra","year":"1994","unstructured":"Ravindra Ahuja, James Orlin, Clifford Stein, and Robert Tarjan. 1994. Improved Algorithms for Bipartite Network Flow. SIAM J. Comput., Vol. 23 (10 1994), 906--933."},{"key":"e_1_2_2_2_1","volume-title":"Graph-based Anomaly Detection and Description: A Survey. CoRR","author":"Akoglu Leman","year":"2014","unstructured":"Leman Akoglu, Hanghang Tong, and Danai Koutra. 2014. Graph-based Anomaly Detection and Description: A Survey. CoRR, Vol. abs\/1404.4679 (2014)."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2470654.2470724"},{"key":"e_1_2_2_4_1","volume-title":"Algorithms and Models for the Web-Graph","author":"Andersen Reid","unstructured":"Reid Andersen and Kumar Chellapilla. 2009. Finding Dense Subgraphs with Size Bounds. In Algorithms and Models for the Web-Graph. Springer Berlin Heidelberg, 25--37."},{"key":"e_1_2_2_5_1","volume-title":"Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '92)","author":"Richard","unstructured":"Richard J. Anderson and Jo ao C. Setubal. 1992. On the Parallel Implementation of Goldberg's Maximum Flow Algorithm. In Proceedings of the Fourth Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA '92). ACM, 168--177."},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_2_10_1","doi-asserted-by":"crossref","unstructured":"Suman Bera Sayan Bhattacharya Jayesh Choudhari and Prantar Ghosh. 2022. A New Dynamic Algorithm for Densest Subhypergraphs.","DOI":"10.1145\/3485447.3512158"},{"key":"e_1_2_2_11_1","volume-title":"Flowless: Extracting Densest Subgraphs Without Flow Computations. In WWW '20: The Web Conference 2020","author":"Boob Digvijay","year":"2020","unstructured":"Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2020. Flowless: Extracting Densest Subgraphs Without Flow Computations. In WWW '20: The Web Conference 2020, Taipei, Taiwan, April 20--24, 2020, Yennun Huang, Irwin King, Tie-Yan Liu, and Maarten van Steen (Eds.). ACM \/ IW3C2, 573--583."},{"key":"e_1_2_2_12_1","volume-title":"Learning and Intelligent Optimization","author":"Brunato Mauro","unstructured":"Mauro Brunato, Holger H. Hoos, and Roberto Battiti. 2008. On Effectively Finding Maximal Quasi-cliques in Graphs. In Learning and Intelligent Optimization. Springer Berlin Heidelberg, 41--55."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_2_14_1","volume-title":"Torres","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri, Kent Quanrud, and Manuel R. Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. 1531--1555."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977172.41"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539100"},{"key":"e_1_2_2_18_1","volume-title":"Disruptions in the US airport network. arXiv","author":"Conti Edoardo","year":"2013","unstructured":"Edoardo Conti, Steve Cao, and AJ Thomas. 2013. Disruptions in the US airport network. arXiv (2013)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_2_20_1","doi-asserted-by":"crossref","unstructured":"Yefim Dinitz. 2006. Dinitz' Algorithm: The Original Version and Even's Version. 218--240.","DOI":"10.1007\/11685654_10"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557142"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.88.062819"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554895"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_2_27_1","volume-title":"Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD","author":"Feng Wenjie","year":"2020","unstructured":"Wenjie Feng, Shenghua Liu, Danai Koutra, Huawei Shen, and Xueqi Cheng. 2020. SpecGreedy: Unified Dense Subgraph Detection. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14--18, 2020, Proceedings, Part I. Springer-Verlag, 181--197."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_2_2_30_1","volume-title":"Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15)","author":"Gionis Aristides","unstructured":"Aristides Gionis and Charalampos E. Tsourakakis. 2015. Dense Subgraph Discovery: KDD 2015 Tutorial. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '15). ACM, 2313--2314."},{"key":"e_1_2_2_31_1","unstructured":"Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.15.3.430"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_2_37_1","volume-title":"Automata, Languages and Programming","author":"Khuller Samir","unstructured":"Samir Khuller and Barna Saha. 2009. On Finding Dense Subgraphs. In Automata, Languages and Programming. Springer Berlin Heidelberg, 597--608."},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335170"},{"key":"e_1_2_2_39_1","doi-asserted-by":"crossref","unstructured":"Victor Lee Ning Ruan Ruoming Jin and Charu Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. 303--336.","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_2_2_40_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483940"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_2_46_1","volume-title":"Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis. arXiv","author":"Manurangsi Pasin","year":"2018","unstructured":"Pasin Manurangsi. 2018. Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis. arXiv, Vol. abs\/1705.03581 (2018)."},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Claire Mathieu and Michel de Rougemont. 2020. Large Very Dense Subgraphs in a Stream of Edges.","DOI":"10.1145\/3412815.3416884"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.98.2.404"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2011.07.001"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2010.03.006"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_2_52_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00548-x"},{"key":"e_1_2_2_55_1","doi-asserted-by":"crossref","unstructured":"Atish Das Sarma Ashwin Lall Danupon Nanongkai and Amitabh Trehan. 2012. Dense Subgraphs on Dynamic Networks.","DOI":"10.1007\/978-3-642-33651-5_11"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(82)90013-X"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(84)90076-2"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344210"},{"key":"e_1_2_2_61_1","unstructured":"Charalampos Tsourakakis and Tianyi Chen. 2021. Dense subgraph discovery: Theory and application. In SDM Tutorial."},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_2_64_1","unstructured":"Johan Ugander Brian Karrer Lars Backstrom and Cameron Marlow. 2011. The Anatomy of the Facebook Social Graph."},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0219633602000117"},{"key":"e_1_2_2_66_1","volume-title":"Weighted Laplacian Method and Its Theoretical Applications. IOP Conference Series: Materials Science and Engineering","volume":"768","author":"Xu Shijie","year":"2020","unstructured":"Shijie Xu, Jiayan Fang, and Xiangyang Li. 2020. Weighted Laplacian Method and Its Theoretical Applications. IOP Conference Series: Materials Science and Engineering, Vol. 768, 7 (2020), 072032."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589314","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3589314","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:46:14Z","timestamp":1750178774000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3589314"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,13]]},"references-count":66,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,13]]}},"alternative-id":["10.1145\/3589314"],"URL":"https:\/\/doi.org\/10.1145\/3589314","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,13]]}}}