{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T06:42:29Z","timestamp":1790750549673,"version":"4.1.0"},"reference-count":79,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T00:00:00Z","timestamp":1636934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Research Grants Council of Hong Kong","award":["17229116 and 17205015"],"award-info":[{"award-number":["17229116 and 17205015"]}]},{"DOI":"10.13039\/501100003803","name":"University of Hong Kong","doi-asserted-by":"crossref","award":["104005858, 104005994"],"award-info":[{"award-number":["104005858, 104005994"]}],"id":[{"id":"10.13039\/501100003803","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Innovation and Technology Commission of Hong Kong","award":["MRP\/029\/18"],"award-info":[{"award-number":["MRP\/029\/18"]}]},{"name":"HKU-TCL Joint Research Center for Artificial Intelligence","award":["200009430"],"award-info":[{"award-number":["200009430"]}]},{"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":"CUHK-SZ","award":["UDF01002139"],"award-info":[{"award-number":["UDF01002139"]}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"ARC","award":["DP200101338 and DP200101116"],"award-info":[{"award-number":["DP200101338 and DP200101116"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            Given a directed graph\n            <jats:italic>G<\/jats:italic>\n            , the directed densest subgraph (DDS) problem refers to the finding of a subgraph from\n            <jats:italic>G<\/jats:italic>\n            , whose density is the highest among all the subgraphs of\n            <jats:italic>G<\/jats:italic>\n            . The DDS problem is fundamental to a wide range of applications, such as fraud detection, community mining, and graph compression. However, existing DDS solutions suffer from efficiency and scalability problems: on a 3,000-edge graph, it takes three days for one of the best exact algorithms to complete. In this article, we develop an efficient and scalable DDS solution. We introduce the notion of [\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            ]-core, which is a dense subgraph for\n            <jats:italic>G<\/jats:italic>\n            , and show that the densest subgraph can be accurately located through the [\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            ]-core with theoretical guarantees. Based on the [\n            <jats:italic>x<\/jats:italic>\n            ,\n            <jats:italic>y<\/jats:italic>\n            ]-core, we develop exact and approximation algorithms. We further study the problems of maintaining the DDS over dynamic directed graphs and finding the weighted DDS on weighted directed graphs, and we develop efficient non-trivial algorithms to solve these two problems by extending our DDS algorithms. We have performed an extensive evaluation of our approaches on 15 real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.\n          <\/jats:p>","DOI":"10.1145\/3483940","type":"journal-article","created":{"date-parts":[[2021,11,15]],"date-time":"2021-11-15T17:48:45Z","timestamp":1636998525000},"page":"1-45","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["On Directed Densest Subgraph Discovery"],"prefix":"10.1145","volume":"46","author":[{"given":"Chenhao","family":"Ma","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Shenzhen, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, B.C., Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney NSW, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,11,15]]},"reference":[{"key":"e_1_3_3_2_2","article-title":"Air Traffic Control System Command Center","author":"Administration Federal Aviation","year":"2019","unstructured":"Federal Aviation Administration. 2019. Air Traffic Control System Command Center. Retrieved from https:\/\/www.faa.gov.","journal-title":"Retrieved from https:\/\/www.faa.gov"},{"key":"e_1_3_3_3_2","doi-asserted-by":"crossref","unstructured":"Ravindra K. Ahuja M. Kodialam A. K. Mishra and J. B. Orlin. 1997. Computational investigations of maximum flow algorithms. European Journal of Operational Research 97 3 (1997) 509\u2013542.","DOI":"10.1016\/S0377-2217(96)00269-X"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1038\/43601"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824780"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_3_8_2","article-title":"An O (m) algorithm for cores decomposition of networks","author":"Batagelj Vladimir","year":"2003","unstructured":"Vladimir Batagelj and Matjaz Zaversnik. 2003. An O (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 (2003).","journal-title":"arXiv preprint cs\/0310049"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/1097029"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036116"},{"key":"e_1_3_3_15_2","first-page":"10","volume-title":"ICWSM","author":"Cha Meeyoung","year":"2010","unstructured":"Meeyoung Cha, Hamed Haddadi, Fabricio Benevenuto, and Krishna P. Gummadi. 2010. Measuring user influence in Twitter: The million follower fallacy. In ICWSM. 10\u201317."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.5555\/3367243.3367353"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137765.3137800"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/3365087"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(97)00016-6"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-012-0539-0"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/894477"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_39"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.5555\/1502110"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_3_3_37_2","first-page":"746","volume-title":"ICDE","author":"Hu Jiafeng","year":"2019","unstructured":"Jiafeng Hu, Reynold Cheng, Kevin Chen-Chuan Chang, Aravind Sankar, Yixiang Fang, and Brian Y. H. Lam. 2019. Discovering maximal motif cliques in large heterogeneous information networks. In ICDE. IEEE, 746\u2013757."},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/3365087"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348556"},{"key":"e_1_3_3_42_2","volume-title":"Analyzing the Structure of Large Graphs","author":"Kannan Ravi","year":"1999","unstructured":"Ravi Kannan and V. Vinay. 1999. Analyzing the Structure of Large Graphs. Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn Bonn."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2365934.2365942"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_3_3_49_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved from http:\/\/snap.stanford.edu\/data.","journal-title":"Retrieved from http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_3_50_2","first-page":"4","article-title":"Motif paths: A new approach for analyzing higher-order semantics between graph nodes","volume":"3","author":"Li Xiaodong","year":"2019","unstructured":"Xiaodong Li, Tsz Nam Chan, Reynold Cheng, Caihua Shan, Chenhao Ma, and Kevin Chang. 2019. Motif paths: A new approach for analyzing higher-order semantics between graph nodes. HKU Tech. Rep. 3 (2019), 4.","journal-title":"HKU Tech. Rep."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447714"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/DASC.2009.130"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_3_58_2","first-page":"1188","volume-title":"ICDM","author":"Miyauchi Atsushi","year":"2018","unstructured":"Atsushi Miyauchi and Akiko Takeda. 2018. Robust densest subgraph discovery. In ICDM. IEEE, 1188\u20131193."},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187863"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.5555\/2063076.2063091"},{"key":"e_1_3_3_61_2","unstructured":"Tore Opsahl. 2011. Why anchorage is not (that) important: Binary ties and sample selection."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2010.03.006"},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_3_3_65_2","article-title":"Network Analysis of Trophic Dynamics in South Florida Ecosystems, FY 99: The Graminoid Ecosystem","author":"Patricio J.","year":"2000","unstructured":"J. Patricio. 2000. Network Analysis of Trophic Dynamics in South Florida Ecosystems, FY 99: The Graminoid Ecosystem. Master\u2019s Thesis. University of Coimbra, Coimbra, Portugal.","journal-title":"Master\u2019s Thesis. University of Coimbra, Coimbra, Portugal"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_42"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.5555\/2888116.2888372"},{"key":"e_1_3_3_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_11"},{"key":"e_1_3_3_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_3_3_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0950-5601(55)80012-3"},{"key":"e_1_3_3_72_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_3_3_73_2","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_3_3_74_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_3_3_75_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_3_76_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_3_77_2","first-page":"378","volume-title":"ECML PKDD","author":"Tsourakakis Charalampos E.","year":"2019","unstructured":"Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura, and Jakub Pachocki. 2019. Novel dense subgraph discovery primitives: Risk aversion and exclusion queries. In ECML PKDD. Springer, 378\u2013394."},{"key":"e_1_3_3_78_2","first-page":"422","volume-title":"ICDE","author":"Zhang Zhiwei","year":"2019","unstructured":"Zhiwei Zhang, Xin Huang, Jianliang Xu, Byron Choi, and Zechao Shang. 2019. Keyword-centric community search. In ICDE. 422\u2013433."},{"key":"e_1_3_3_79_2","first-page":"156","volume-title":"ICSC","author":"Zheng Dong","year":"2017","unstructured":"Dong Zheng, Jianquan Liu, Rong-Hua Li, Cigdem Aslay, Yi-Cheng Chen, and Xin Huang. 2017. Querying intimate-core groups in weighted graphs. In ICSC. 156\u2013163."},{"key":"e_1_3_3_80_2","first-page":"22","volume-title":"WWW","author":"Ziegler Cai-Nicolas","year":"2005","unstructured":"Cai-Nicolas Ziegler, Sean M. McNee, Joseph A. Konstan, and Georg Lausen. 2005. Improving recommendation lists through topic diversification. In WWW. 22\u201332."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3483940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3483940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:13Z","timestamp":1750191433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3483940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,15]]},"references-count":79,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3483940"],"URL":"https:\/\/doi.org\/10.1145\/3483940","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,11,15]]},"assertion":[{"value":"2020-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}