{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,8]],"date-time":"2026-08-08T17:37:03Z","timestamp":1786210623953,"version":"3.56.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p>\n            The problem of finding densest subgraphs has received increasing attention in recent years finding applications in biology, finance, as well as social network analysis. The\n            <jats:italic>k<\/jats:italic>\n            -clique densest subgraph problem is a generalization of the densest subgraph problem, where the objective is to find a subgraph maximizing the ratio between the number of\n            <jats:italic>k<\/jats:italic>\n            -cliques in the subgraph and its number of nodes. It includes as a special case the problem of finding subgraphs with largest average number of triangles (\n            <jats:italic>k<\/jats:italic>\n            = 3), which plays an important role in social network analysis. Moreover, algorithms that deal with larger values of\n            <jats:italic>k<\/jats:italic>\n            can effectively find quasi-cliques. The densest subgraph problem can be solved in polynomial time with algorithms based on maximum flow, linear programming or a recent approach based on convex optimization. In particular, the latter approach can scale to graphs containing tens of billions of edges. While finding a densest subgraph in large graphs is no longer a bottleneck, the\n            <jats:italic>k<\/jats:italic>\n            -clique densest subgraph remains challenging even when\n            <jats:italic>k<\/jats:italic>\n            = 3. Our work aims at developing near-optimal and exact algorithms for the\n            <jats:italic>k<\/jats:italic>\n            -clique densest subgraph problem on large real-world graphs. We give a surprisingly simple procedure that can be employed to find the maximal\n            <jats:italic>k<\/jats:italic>\n            -clique densest subgraph in large-real world graphs. By leveraging appealing properties of existing results, we combine it with a recent approach for listing all\n            <jats:italic>k<\/jats:italic>\n            -cliques in a graph and a sampling scheme, obtaining the state-of-the-art approaches for the aforementioned problem. Our theoretical results are complemented with an extensive experimental evaluation showing the effectiveness of our approach in large real-world graphs.\n          <\/jats:p>","DOI":"10.14778\/3401960.3401962","type":"journal-article","created":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T19:15:14Z","timestamp":1615403714000},"page":"1628-1640","source":"Crossref","is-referenced-by-count":47,"title":["KClist++"],"prefix":"10.14778","volume":"13","author":[{"given":"Bintao","family":"Sun","sequence":"first","affiliation":[{"name":"The University of Hong Kong, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Maximilien","family":"Danisch","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"T-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"The University of Hong Kong, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[{"name":"Telecom Paris, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,3,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/646389.690506"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1214\/14-AAP1091"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"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.14778\/2140436.2140442"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646688.702972"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545503"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186125"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557142"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2794080"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/894477"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.59935"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1034968065"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/3042817.3042867"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052636"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3336191.3371839"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1738952"},{"key":"e_1_2_1_24_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014.  J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http:\/\/snap.stanford.edu\/data June 2014."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/14100018X"},{"key":"e_1_2_1_27_1","volume-title":"The. Pearson Education","author":"Siek J. G.","year":"2001","unstructured":"J. G. Siek , L.-Q. Lee , and A. Lumsdaine . Boost Graph Library: User Guide and Reference Manual , The. Pearson Education , 2001 . J. G. Siek, L.-Q. Lee, and A. Lumsdaine. Boost Graph Library: User Guide and Reference Manual, The. Pearson Education, 2001."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3401960.3401962","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:11:05Z","timestamp":1672225865000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3401960.3401962"}},"subtitle":["a simple algorithm for finding k-clique densest subgraphs in large graphs"],"short-title":[],"issued":{"date-parts":[[2020,6]]},"references-count":32,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.14778\/3401960.3401962"],"URL":"https:\/\/doi.org\/10.14778\/3401960.3401962","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,6]]}}}