{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,4]],"date-time":"2026-09-04T00:44:01Z","timestamp":1788482641562,"version":"build-2803163510"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>\n                    Finding the densest subgraph (DS) from a graph is a fundamental problem in graph databases. The DS obtained, which reveals closely related entities, has been found to be useful in various application domains such as e-commerce, social science, and biology. However, in a big graph that contains billions of edges, it is desirable to find more than one subgraph cluster that are not necessarily the densest, yet they reveal closely-related vertices. In this paper, we study the locally densest subgraph (LDS), a recently-proposed variant of DS. An LDS is a subgraph which is the densest among the \"local neighbors\". Given a graph\n                    <jats:italic>G<\/jats:italic>\n                    , a number of LDS's can be returned, which reflect different dense regions of\n                    <jats:italic>G<\/jats:italic>\n                    and thus give more information than DS. The existing LDS solution suffers from low efficiency. We thus develop a convex-programming-based solution that enables powerful pruning. Extensive experiments on seven real large graph datasets show that our proposed algorithm is up to four orders of magnitude faster than the state-of-the-art.\n                  <\/jats:p>","DOI":"10.14778\/3551793.3551826","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T18:25:03Z","timestamp":1664475903000},"page":"2719-2732","source":"Crossref","is-referenced-by-count":21,"title":["Finding locally densest subgraphs"],"prefix":"10.14778","volume":"15","author":[{"given":"Chenhao","family":"Ma","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Reynold","family":"Cheng","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"The University of British Columbia, Vancouver, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaolin","family":"Han","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Statistical mechanics of complex networks. Reviews of modern physics 74, 1","author":"Albert R\u00e9ka","year":"2002","unstructured":"R\u00e9ka Albert and Albert-L\u00e1szl\u00f3 Barab\u00e1si . 2002. Statistical mechanics of complex networks. Reviews of modern physics 74, 1 ( 2002 ), 47. R\u00e9ka Albert and Albert-L\u00e1szl\u00f3 Barab\u00e1si. 2002. Statistical mechanics of complex networks. Reviews of modern physics 74, 1 (2002), 47."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_1_5_1","volume-title":"Densest subgraph in streaming and mapreduce. PVLDB","author":"Bahmani Bahman","year":"2012","unstructured":"Bahman Bahmani , Ravi Kumar , and Sergei Vassilvitskii . 2012. Densest subgraph in streaming and mapreduce. PVLDB ( 2012 ). Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest subgraph in streaming and mapreduce. PVLDB (2012)."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380033"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_11_1","volume-title":"Densest Subgraph: Supermodularity, Iterative Peeling, and Flow","author":"Chekuri Chandra","year":"2022","unstructured":"Chandra Chekuri , Kent Quanrud , and Manuel R Torres . 2022 . Densest Subgraph: Supermodularity, Iterative Peeling, and Flow . In SODA. SIAM , 1531--1555. Chandra Chekuri, Kent Quanrud, and Manuel R Torres. 2022. Densest Subgraph: Supermodularity, Iterative Peeling, and Flow. In SODA. SIAM, 1531--1555."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824077"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220093"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41109-021-00381-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00664-3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the VLDB Endowment 15","author":"Fang Yixiang","year":"2022","unstructured":"Yixiang Fang , Wensheng Luo , and Chenhao Ma . 2022 . Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques . Proceedings of the VLDB Endowment 15 (2022). Yixiang Fang, Wensheng Luo, and Chenhao Ma. 2022. Densest Subgraph Discovery on Large Graphs: Applications, Challenges, and Techniques. Proceedings of the VLDB Endowment 15 (2022)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Marguerite Frank Philip Wolfe etal 1956. An algorithm for quadratic programming. Naval research logistics quarterly 3 1--2 (1956) 95--110.  Marguerite Frank Philip Wolfe et al. 1956. An algorithm for quadratic programming. Naval research logistics quarterly 3 1--2 (1956) 95--110.","DOI":"10.1002\/nav.3800030109"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_2_1_26_1","volume-title":"Finding a maximum density subgraph","author":"Goldberg Andrew V","unstructured":"Andrew V Goldberg . 1984. Finding a maximum density subgraph . University of California Berkeley . Andrew V Goldberg. 1984. Finding a maximum density subgraph. University of California Berkeley."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2019.00-22"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977172.8"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/3523210.3523225"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.websem.2021.100696"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00190"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_34_1","unstructured":"Ravindran Kannan and V Vinay. 1999. Analyzing the structure of large graphs. Forschungsinst. f\u00fcr Diskrete Mathematik.  Ravindran Kannan and V Vinay. 1999. Analyzing the structure of large graphs. Forschungsinst. f\u00fcr Diskrete Mathematik."},{"key":"e_1_2_1_35_1","volume-title":"International colloquium on automata, languages, and programming","author":"Khuller Samir","unstructured":"Samir Khuller and Barna Saha . 2009. On finding dense subgraphs . In International colloquium on automata, languages, and programming . Springer , 597--608. Samir Khuller and Barna Saha. 2009. On finding dense subgraphs. In International colloquium on automata, languages, and programming. Springer, 597--608."},{"key":"e_1_2_1_36_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data.  Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447714"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3364324.3364330"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3483940"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher Jakub Pachocki Richard Peng Charalampos Tsourakakis and Shen Chen Xu. 2015. Scalable large near-clique detection in large-scale networks via sampling. In KDD. 815--824.  Michael Mitzenmacher Jakub Pachocki Richard Peng Charalampos 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_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488705"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_46_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. https:\/\/networkrepository.com Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https:\/\/networkrepository.com"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192431"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_2_1_50_1","volume-title":"Network structure and minimum degree. Social networks 5, 3","author":"Seidman Stephen B","year":"1983","unstructured":"Stephen B Seidman . 1983. Network structure and minimum degree. Social networks 5, 3 ( 1983 ), 269--287. Stephen B Seidman. 1983. Network structure and minimum degree. Social networks 5, 3 (1983), 269--287."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cell.2005.08.029"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_54_1","doi-asserted-by":"crossref","unstructured":"Charalampos Tsourakakis. 2015. The k-clique densest subgraph problem. In WWW. 1122--1132.  Charalampos Tsourakakis. 2015. The k-clique densest subgraph problem. In WWW. 1122--1132.","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_56_1","unstructured":"Charalampos Tsourakakis and Tianyi Chen. 2021. Dense subgraph discovery: Theory and application. In SDM Tutorial.  Charalampos Tsourakakis and Tianyi Chen. 2021. Dense subgraph discovery: Theory and application. In SDM Tutorial."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551826","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T05:36:06Z","timestamp":1672205766000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551826"}},"subtitle":["a convex programming approach"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":58,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551826"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551826","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}