{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T05:39:16Z","timestamp":1768109956082,"version":"3.49.0"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2021,6,15]]},"abstract":"<jats:p>Given a directed graph G, the directed densest subgraph (DDS) problem refers to the finding of a subgraph from G, whose density is the highest among all the subgraphs of G. 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 threethousand- edge graph, it takes three days for one of the best exact algorithms to complete. In this paper, we develop an efficient and scalable DDS solution. We introduce the notion of [x, y]-core, which is a dense subgraph for G, and show that the densest subgraph can be accurately located through the [x, y]-core with theoretical guarantees. Based on the [x, y]-core, we develop both exact and approximation algorithms. We have performed an extensive evaluation of our approaches on eight real large datasets. The results show that our proposed solutions are up to six orders of magnitude faster than the state-of-the-art.<\/jats:p>","DOI":"10.1145\/3471485.3471494","type":"journal-article","created":{"date-parts":[[2021,6,18]],"date-time":"2021-06-18T05:22:06Z","timestamp":1623993726000},"page":"33-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Efficient Directed Densest Subgraph Discovery"],"prefix":"10.1145","volume":"50","author":[{"given":"Chenhao","family":"Ma","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}]},{"given":"Yixiang","family":"Fang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong, Hong Kong , China"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong, China"}]},{"given":"Laks V.S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Canada"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales, Australia"}]}],"member":"320","published-online":{"date-parts":[[2021,6,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Internet: Diameter of the world-wide web. nature, 401(6749):130","author":"Albert R.","year":"1999","unstructured":"R. Albert , H. Jeong , and A.-L. Barab\u00b4asi . Internet: Diameter of the world-wide web. nature, 401(6749):130 , 1999 . R. Albert, H. Jeong, and A.-L. Barab\u00b4asi. Internet: Diameter of the world-wide web. nature, 401(6749):130, 1999."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_3_1","volume-title":"An o(m) algorithm for cores decomposition of networks","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik . An o(m) algorithm for cores decomposition of networks . 2003 . V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. 2003."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.74.036116"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/894477"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/1502110"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1348549.1348556"},{"key":"e_1_2_1_13_1","volume-title":"Analyzing the structure of large graphs","author":"Kannan R.","year":"1999","unstructured":"R. Kannan and V. Vinay . Analyzing the structure of large graphs . University of Bonn , 1999 . R. Kannan and V. Vinay. Analyzing the structure of large graphs. University of Bonn, 1999."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_42"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90028-X"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471494","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3471485.3471494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:26Z","timestamp":1750191446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3471485.3471494"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,6,15]]}},"alternative-id":["10.1145\/3471485.3471494"],"URL":"https:\/\/doi.org\/10.1145\/3471485.3471494","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}