{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T13:08:34Z","timestamp":1775912914808,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2024,12,18]],"date-time":"2024-12-18T00:00:00Z","timestamp":1734480000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12071478, 61972404"],"award-info":[{"award-number":["12071478, 61972404"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,12,18]]},"abstract":"<jats:p>\n                    Detecting locally, non-overlapping, near-clique densest subgraphs is a crucial problem for community search in social networks. As a vertex may be involved in multiple overlapped local cliques, detecting locally densest sub-structures considering\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    -clique density, i.e.,\n                    <jats:italic toggle=\"yes\">locally h-clique densest subgraph (LhCDS)<\/jats:italic>\n                    attracts great interests. This paper investigates the L\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    CDS detection problem and proposes an efficient and exact algorithm to list the top-\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    non-overlapping, locally\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    -clique dense, and compact subgraphs. We in particular jointly consider\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    -clique compact number and L\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    CDS and design a new ''Iterative Propose-Prune-and-Verify'' pipeline\n                    <jats:italic toggle=\"yes\">(IPPV)<\/jats:italic>\n                    for top-\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    L\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    CDS detection. (1) In the proposal part, we derive initial bounds for\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    -clique compact numbers; prove the validity, and extend a convex programming method to tighten the bounds for proposing L\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    CDS candidates without missing any. (2) Then a tentative graph decomposition method is proposed to solve the challenging case where a clique spans multiple subgraphs in graph decomposition. (3) To deal with the verification difficulty, both a basic and a fast verification method are proposed, where the fast method constructs a smaller-scale flow network to improve efficiency while preserving the verification correctness. The verified L\n                    <jats:italic toggle=\"yes\">h<\/jats:italic>\n                    CDSes are returned, while the candidates that remained unsure reenter the\n                    <jats:italic toggle=\"yes\">IPPV<\/jats:italic>\n                    pipeline. (4) We further extend the proposed methods to locally more general pattern densest subgraph detection problems. We prove the exactness and low complexity of the proposed algorithm. Extensive experiments on real datasets show the effectiveness and high efficiency of\n                    <jats:italic toggle=\"yes\">IPPV.<\/jats:italic>\n                    Codes are available at: https:\/\/github.com\/Elssky\/IPPV\n                  <\/jats:p>","DOI":"10.1145\/3698800","type":"journal-article","created":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:40:35Z","timestamp":1734712835000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["An Efficient and Exact Algorithm for Locally\n                    <i>h<\/i>\n                    -Clique Densest Subgraph Discovery"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9949-9451","authenticated-orcid":false,"given":"Xiaojia","family":"Xu","sequence":"first","affiliation":[{"name":"Renmin University of China, Beijing, CN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-5748-0141","authenticated-orcid":false,"given":"Haoyu","family":"Liu","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, CN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6544-1515","authenticated-orcid":false,"given":"Xiaowei","family":"Lv","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, CN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4197-2258","authenticated-orcid":false,"given":"Yongcai","family":"Wang","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, CN"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7748-5427","authenticated-orcid":false,"given":"Deying","family":"Li","sequence":"additional","affiliation":[{"name":"Renmin University of China, Beijing, CN"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,12,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0340-z"},{"key":"e_1_2_1_2_1","volume-title":"Densest Subgraph in Streaming and MapReduce. ArXiv","author":"Bahmani Bahman","year":"2012","unstructured":"Bahman Bahmani, Ravi Kumar, and Sergei Vassilvitskii. 2012. Densest Subgraph in Streaming and MapReduce. ArXiv, Vol. abs\/1201.6567 (2012)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of The Web Conference 2020","author":"Boob Digvijay","year":"2019","unstructured":"Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, and Junxing Wang. 2019. Flowless: Extracting Densest Subgraphs Without Flow Computations. Proceedings of The Web Conference 2020 (2019)."},{"key":"e_1_2_1_5_1","first-page":"1859","article-title":"Convex Optimization","volume":"51","author":"Boyd Stephen P.","year":"2010","unstructured":"Stephen P. Boyd and Lieven Vandenberghe. 2010. Convex Optimization. IEEE Trans. Automat. Control, Vol. 51 (2010), 1859--1859. https:\/\/api.semanticscholar.org\/CorpusID:37925315","journal-title":"IEEE Trans. Automat. Control"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_2_1_7_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. In ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565843"},{"key":"e_1_2_1_12_1","volume-title":"Discovering Large Dense Subgraphs in Massive Graphs. In Very Large Data Bases Conference. https:\/\/api.semanticscholar.org\/CorpusID:120822","author":"Gibson David","year":"2005","unstructured":"David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering Large Dense Subgraphs in Massive Graphs. In Very Large Data Bases Conference. https:\/\/api.semanticscholar.org\/CorpusID:120822"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_2_1_14_1","volume-title":"Technical report","author":"Goldberg Andrew V.","unstructured":"Andrew V. Goldberg. 1984. Finding a Maximum Density Subgraph. In Technical report,University of California, Berkeley."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/113198.113200"},{"key":"e_1_2_1_16_1","unstructured":"Elfarouk Harb Kent Quanrud and Chandra Chekuri. 2022. Faster and Scalable Algorithms for Densest Subgraph and Decomposition. In Neural Information Processing Systems."},{"key":"e_1_2_1_17_1","volume-title":"Discovering Maximal Motif Cliques in Large Heterogeneous Information Networks. 2019 IEEE 35th International Conference on Data Engineering (ICDE) (2019","author":"Hu Jiafeng","year":"2019","unstructured":"Jiafeng Hu, Reynold Cheng, Kevin Chen-Chuan Chang, Aravind Sankar, Yixiang Fang, and Brian Yee Hong Lam. 2019. Discovering Maximal Motif Cliques in Large Heterogeneous Information Networks. 2019 IEEE 35th International Conference on Data Engineering (ICDE) (2019), 746--757. https:\/\/api.semanticscholar.org\/CorpusID:174819659"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_19_1","unstructured":"Valdis Krebs. 2004. Books about US politics. Unpublished. http:\/\/www.orgnet.com\/"},{"key":"e_1_2_1_20_1","volume-title":"A survey on the densest subgraph problem and its variants. arXiv preprint arXiv:2303.14467","author":"Lanciano Tommaso","year":"2023","unstructured":"Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, and Francesco Bonchi. 2023. A survey on the densest subgraph problem and its variants. arXiv preprint arXiv:2303.14467 (2023)."},{"key":"e_1_2_1_21_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_22_1","volume-title":"Pacific-Asia Conference on Knowledge Discovery and Data Mining. https:\/\/api.semanticscholar.org\/CorpusID:332896","author":"Leskovec Jure","unstructured":"Jure Leskovec, Ajit Singh, and Jon M. Kleinberg. 2006. Patterns of Influence in a Recommendation Network. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. https:\/\/api.semanticscholar.org\/CorpusID:332896"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-022-04996-1"},{"key":"e_1_2_1_24_1","volume-title":"Graph summarization methods and applications: A survey. ACM computing surveys (CSUR)","author":"Liu Yike","year":"2018","unstructured":"Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. 2018. Graph summarization methods and applications: A survey. ACM computing surveys (CSUR), Vol. 51, 3 (2018), 1--34."},{"key":"e_1_2_1_25_1","volume-title":"A Survey of Densest Subgraph Discovery on Large Graphs. arXiv preprint arXiv:2306.07927","author":"Luo Wensheng","year":"2023","unstructured":"Wensheng Luo, Chenhao Ma, Yixiang Fang, and Laks VS Lakshman. 2023. A Survey of Densest Subgraph Discovery on Large Graphs. arXiv preprint arXiv:2306.07927 (2023)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_31_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"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/3192424.3192431"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2032324100"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00008"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487689"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1038\/ng1242"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/2535568.2448942"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of MLG Workshop.","author":"Zou Zhaonian","year":"2013","unstructured":"Zhaonian Zou. 2013. Polynomial-time algorithm for finding densest subgraphs in uncertain graphs. In Proceedings of MLG Workshop."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698800","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3698800","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:46:11Z","timestamp":1774979171000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3698800"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,18]]},"references-count":43,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12,18]]}},"alternative-id":["10.1145\/3698800"],"URL":"https:\/\/doi.org\/10.1145\/3698800","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,18]]}}}