{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:44:35Z","timestamp":1788482675068,"version":"build-2803163510"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>\n                    <jats:italic>Densest subgraph discovery<\/jats:italic>\n                    (DSD) is a fundamental problem in graph mining. It has been studied for decades, and is widely used in various areas, including network science, biological analysis, and graph databases. Given a graph\n                    <jats:italic>G<\/jats:italic>\n                    , DSD aims to find a subgraph\n                    <jats:italic>D<\/jats:italic>\n                    of\n                    <jats:italic>G<\/jats:italic>\n                    with the highest density (e.g., the number of edges over the number of vertices in\n                    <jats:italic>D<\/jats:italic>\n                    ). Because DSD is difficult to solve, we propose a new solution paradigm in this paper. Our main observation is that the densest subgraph can be accurately found through a\n                    <jats:italic>k<\/jats:italic>\n                    -core (a kind of dense subgraph of\n                    <jats:italic>G<\/jats:italic>\n                    ), with theoretical guarantees. Based on this intuition, we develop efficient exact and approximation solutions for DSD. Moreover, our solutions are able to find the densest subgraphs for a wide range of graph density definitions, including clique-based- and general pattern-based density. We have performed extensive experimental evaluation on both real and synthetic datasets. Our results show that our algorithms are up to four orders of magnitude faster than existing approaches.\n                  <\/jats:p>","DOI":"10.14778\/3342263.3342645","type":"journal-article","created":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T14:36:11Z","timestamp":1568817371000},"page":"1719-1732","source":"Crossref","is-referenced-by-count":102,"title":["Efficient algorithms for densest subgraph discovery"],"prefix":"10.14778","volume":"12","author":[{"given":"Yixiang","family":"Fang","sequence":"first","affiliation":[{"name":"Guangzhou University, China and The University of New South Wales, Australia and Zhejiang Lab, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaiqiang","family":"Yu","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"The University of New South Wales, Australia and Zhejiang Lab, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/en.wikipedia.org\/wiki\/Clique_(graph_theory).  https:\/\/en.wikipedia.org\/wiki\/Clique_(graph_theory)."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791199334"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_2_1_7_1","volume-title":"An o(m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049","author":"Batagelj V.","year":"2003","unstructured":"V. Batagelj and M. Zaversnik . An o(m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 , 2003 . V. Batagelj and M. Zaversnik. An o(m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049, 2003."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_2_1_10_1","first-page":"84","volume-title":"APPROX","author":"Charikar M.","year":"2000","unstructured":"M. Charikar . Greedy approximation algorithms for finding dense components in a graph . In APPROX , pages 84 -- 95 . Springer , 2000 . M. Charikar. Greedy approximation algorithms for finding dense components in a graph. In APPROX, pages 84--95. Springer, 2000."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2882837"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403098"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-017-0482-5"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00035"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2845414"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2872982"},{"key":"e_1_2_1_27_1","volume-title":"Efficient algorithms for densest subgraph discovery (technical report). arXiv","author":"Fang Y.","year":"2019","unstructured":"Y. Fang , K. Yu , R. Cheng , L. V. S. Lakshmanan , and X. Lin . Efficient algorithms for densest subgraph discovery (technical report). arXiv , 2019 . https:\/\/arxiv.org\/abs\/1906.00341. Y. Fang, K. Yu, R. Cheng, L. V. S. Lakshmanan, and X. Lin. Efficient algorithms for densest subgraph discovery (technical report). arXiv, 2019. https:\/\/arxiv.org\/abs\/1906.00341."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_2_1_32_1","volume-title":"UC Berkeley","author":"Goldberg A. V.","year":"1984","unstructured":"A. V. Goldberg . Finding a maximum density subgraph . UC Berkeley , 1984 . A. V. Goldberg. Finding a maximum density subgraph. UC Berkeley, 1984."},{"key":"e_1_2_1_33_1","unstructured":"G. T. Heineman G. Pollice and S. Selkow. Chapter 8: Network flow algorithms. Algorithms in a Nutshell pages 226--250 2008.  G. T. Heineman G. Pollice and S. Selkow. Chapter 8: Network flow algorithms. Algorithms in a Nutshell pages 226--250 2008."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00072"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983323.2983748"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2730873"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882913"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741101"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31849"},{"key":"e_1_2_1_43_1","volume-title":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","author":"Kannan R.","year":"1999","unstructured":"R. Kannan and V. Vinay . Analyzing the structure of large graphs . Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn , 1999 . R. Kannan and V. Vinay. Analyzing the structure of large graphs. Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn, 1999."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021937"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11731139_44"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms10168"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2017.8258018"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2012.124"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00110"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPDC.2005.4"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149198"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164139"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192431"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021927"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.14778\/3275536.3275540"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3057742"},{"key":"e_1_2_1_62_1","volume-title":"Network structure and minimum degree. Social networks","author":"Seidman S. B.","year":"1983","unstructured":"S. B. Seidman . Network structure and minimum degree. Social networks , 1983 . S. B. Seidman. Network structure and minimum degree. Social networks, 1983."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1080\/0022250X.1978.9989883"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1038\/ng1242"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.35"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3342263.3342645","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:59:00Z","timestamp":1672203540000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3342263.3342645"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":70,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["10.14778\/3342263.3342645"],"URL":"https:\/\/doi.org\/10.14778\/3342263.3342645","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}