{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T00:41:32Z","timestamp":1789000892801,"version":"build-2803163510"},"reference-count":232,"publisher":"Association for Computing Machinery (ACM)","issue":"8","license":[{"start":{"date-parts":[[2024,4,30]],"date-time":"2024-04-30T00:00:00Z","timestamp":1714435200000},"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":["ACM Comput. Surv."],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>The Densest Subgraph Problem requires us to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature since the early 1970s, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest in this problem with several important contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention to the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.<\/jats:p>","DOI":"10.1145\/3653298","type":"journal-article","created":{"date-parts":[[2024,3,22]],"date-time":"2024-03-22T12:03:05Z","timestamp":1711108985000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["A Survey on the Densest Subgraph Problem and its Variants"],"prefix":"10.1145","volume":"56","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3822-4419","authenticated-orcid":false,"given":"Tommaso","family":"Lanciano","sequence":"first","affiliation":[{"name":"KTH Royal Institute of Technology, Stockholm, Sweden and Sapienza University, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6033-6433","authenticated-orcid":false,"given":"Atsushi","family":"Miyauchi","sequence":"additional","affiliation":[{"name":"CENTAI Institute, Turin, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3062-4485","authenticated-orcid":false,"given":"Adriano","family":"Fazzone","sequence":"additional","affiliation":[{"name":"CENTAI Institute, Turin Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-8315","authenticated-orcid":false,"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"CENTAI Institute, Turin Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,4,30]]},"reference":[{"issue":"3","key":"e_1_3_2_2_2","first-page":"74","article-title":"The wedge picking model: A theoretical analysis of graph evolution caused by triadic closure and algorithmic implications","volume":"16","author":"Ahmadian S.","year":"2021","unstructured":"S. Ahmadian and S. Haddadan. 2021. The wedge picking model: A theoretical analysis of graph evolution caused by triadic closure and algorithmic implications. J. Strateg. Innov. Sust. 16, 3 (2021), 74\u201393.","journal-title":"J. Strateg. Innov. Sust."},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412036"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2012.v008a006"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225140"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.121.030503"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.05.011"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13123-8_6"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1137\/15M1050574"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512158"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.02.034"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.34"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2007.12.007"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39053-1_5"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.101"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.4337\/9781035304998.00010"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s43069-020-00020-5"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/WI.2016.0032"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.3233\/WEB-190412"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.2200\/S01163ED1V01Y202201DMK019"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2021.08.032"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3324962"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_3_2_32_2","first-page":"15253","volume-title":"Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS\u201919)","author":"Boob D.","year":"2019","unstructured":"D. Boob, S. Sawlani, and D. Wang. 2019. Faster width-dependent algorithm for mixed packing and covering LPs. In Proceedings of the 33rd Conference on Neural Information Processing Systems (NeurIPS\u201919). 15253\u201315262."},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36065-7_12"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.86"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.03.008"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-49487-6_4"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0016"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm086"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.5555\/3317280"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICS51289.2020.00034"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_3_2_42_2","article-title":"On finding dense common subgraphs","volume":"1802","author":"Charikar M.","year":"2018","unstructured":"M. Charikar, Y. Naamad, and J. Wu. 2018. On finding dense common subgraphs. CoRR abs\/1802.06361.","journal-title":"CoRR"},{"key":"e_1_3_2_43_2","article-title":"(1- \\(\\epsilon\\) )-approximate fully dynamic densest subgraph: Linear space and faster update time","volume":"2210","author":"Chekuri C.","year":"2022","unstructured":"C. Chekuri and K. Quanrud. 2022. (1- \\(\\epsilon\\) )-approximate fully dynamic densest subgraph: Linear space and faster update time. CoRR abs\/2210.02611.","journal-title":"CoRR"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.64"},{"key":"e_1_3_2_45_2","article-title":"On the generalized mean densest subgraph problem: Complexity and algorithms","author":"Chekuri C.","year":"2023","unstructured":"C. Chekuri and M. R. Torres. 2023. On the generalized mean densest subgraph problem: Complexity and algorithms. arXiv:2306.02172. Retrieved from https:\/\/arxiv.org\/abs\/2306.02172","journal-title":"arXiv:2306.02172"},{"key":"e_1_3_2_46_2","first-page":"83","volume-title":"Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA\u201910)","author":"Chen D. Z.","year":"2010","unstructured":"D. Z. Chen, R. Fleischer, and J. Li. 2010. Densest k-subgraph approximation on intersection graphs. In Proceedings of the 8th International Workshop on Approximation and Online Algorithms (WAOA\u201910). 83\u201393."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_3_2_48_2","first-page":"379","volume-title":"Proceedings of the 28th Conference on Neural Information Processing Systems (NIPS\u201914)","author":"Chen S.","year":"2014","unstructured":"S. Chen, T. Lin, I. King, M. R. Lyu, and W. Chen. 2014. Combinatorial pure exploration of multi-armed bandits. In Proceedings of the 28th Conference on Neural Information Processing Systems (NIPS\u201914). 379\u2013387."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977172.41"},{"key":"e_1_3_2_50_2","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201922)","author":"Chen T.","year":"2022","unstructured":"T. Chen, B. Matejek, M. Mitzenmacher, and C.E. Tsourakakis. 2022. Algorithmic tools for understanding the motif structure of networks. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201922)."},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539100"},{"key":"e_1_3_2_52_2","first-page":"151","volume-title":"Proceedings of the 30th International Conference on Machine Learning (ICML\u201913)","author":"Chen W.","year":"2013","unstructured":"W. Chen, Y. Wang, and Y. Yuan. 2013. Combinatorial multi-armed bandit: General framework and applications. In Proceedings of the 30th International Conference on Machine Learning (ICML\u201913). 151\u2013159."},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791278376"},{"key":"e_1_3_2_54_2","first-page":"150","volume-title":"Proceedings of the Joint Annual RECOMB Satellite Workshops on Systems Biology and on Regulatory Genomics","author":"Chesler E. J.","year":"2005","unstructured":"E. J. Chesler and M. A. Langston. 2005. Combinatorial genetic regulatory network analysis tools for high throughput transcriptomic data. In Proceedings of the Joint Annual RECOMB Satellite Workshops on Systems Biology and on Regulatory Genomics. 150\u2013165."},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096402"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.110"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00090"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.14778\/3358701.3358704"},{"key":"e_1_3_2_59_2","first-page":"38:1\u201338:23","volume-title":"Proceedings of the 14th Conference on Innovations in Theoretical Computer Science (ITCS\u201923)","author":"Chuzhoy J.","year":"2023","unstructured":"J. Chuzhoy, M. Dalirrooyfard, V. Grinberg, and Z. Tan. 2023. A new conjecture on hardness of 2-CSP\u2019s with implications to hardness of densest k-subgraph and other problems. In Proceedings of the 14th Conference on Innovations in Theoretical Computer Science (ITCS\u201923). 38:1\u201338:23."},{"key":"e_1_3_2_60_2","first-page":"937","volume-title":"Proceedings of the 13th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Cohen E.","year":"2002","unstructured":"E. Cohen, E. Halperin, H. Kaplan, and U. Zwick. 2002. Reachability and distance queries via 2-hop labels. In Proceedings of the 13th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201902). 937\u2013946."},{"key":"e_1_3_2_61_2","first-page":"11615","volume-title":"Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS\u201922)","author":"Corinzia L.","year":"2022","unstructured":"L. Corinzia, P. Penna, W. Szpankowski, and J. Buhmann. 2022. Statistical and computational thresholds for the planted k-densest sub-hypergraph problem. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS\u201922). 11615\u201311640."},{"key":"e_1_3_2_62_2","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2022","unstructured":"T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein. 2022. Introduction to Algorithms, 4th edition. MIT Press."},{"key":"e_1_3_2_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807099"},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3"},{"key":"e_1_3_2_65_2","first-page":"151","volume-title":"Proceedings of the 26th International Symposium on Distributed Computing (DISC\u201912)","author":"Sarma A. D.","year":"2012","unstructured":"A. D. Sarma, A. Lall, D. Nanongkai, and A. Trehan. 2012. Dense subgraphs on dynamic networks. In Proceedings of the 26th International Symposium on Distributed Computing (DISC\u201912). 151\u2013165."},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517890"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3265009"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.13.7.492"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/s42979-021-00593-w"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/1513876.1513879"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_3_2_73_2","doi-asserted-by":"publisher","DOI":"10.1145\/2935764.2935813"},{"key":"e_1_3_2_74_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00011"},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl260"},{"key":"e_1_3_2_76_2","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554895"},{"key":"e_1_3_2_77_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97568-5"},{"key":"e_1_3_2_78_2","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342645"},{"key":"e_1_3_2_79_2","doi-asserted-by":"publisher","DOI":"10.3390\/a12080157"},{"key":"e_1_3_2_80_2","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565843"},{"key":"e_1_3_2_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509985"},{"key":"e_1_3_2_82_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_3_2_83_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1183"},{"key":"e_1_3_2_84_2","doi-asserted-by":"publisher","DOI":"10.5555\/903587"},{"key":"e_1_3_2_85_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2010.78"},{"key":"e_1_3_2_86_2","first-page":"181","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201920)","author":"Feng W.","year":"2020","unstructured":"W. Feng, S. Liu, D. Koutra, H. Shen, and X. Cheng. 2020. SpecGreedy: Unified dense subgraph detection. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201920). 181\u2013197."},{"key":"e_1_3_2_87_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_3_2_88_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_3_2_89_2","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular Functions and Optimization","author":"Fujishige S.","year":"2005","unstructured":"S. Fujishige. 2005. Submodular Functions and Optimization. Annals of Discrete Mathematics, Vol. 58. Elsevier."},{"key":"e_1_3_2_90_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.15"},{"key":"e_1_3_2_91_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132993"},{"key":"e_1_3_2_92_2","doi-asserted-by":"publisher","DOI":"10.1145\/3369872"},{"key":"e_1_3_2_93_2","doi-asserted-by":"publisher","DOI":"10.1137\/0218003"},{"key":"e_1_3_2_94_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00239"},{"key":"e_1_3_2_95_2","first-page":"2201","volume-title":"Proceedings of the 36th International Conference on Machine Learning (ICML\u201919)","author":"Ghaffari M.","year":"2019","unstructured":"M. Ghaffari, Silvio Lattanzi, and S. Mitrovi\u0107. 2019. Improved parallel algorithms for density-based network clustering. In Proceedings of the 36th International Conference on Machine Learning (ICML\u201919). 2201\u20132210."},{"key":"e_1_3_2_96_2","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_3_2_97_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2789987"},{"key":"e_1_3_2_98_2","article-title":"Mathematical programming and approximation algorithms","author":"Goemans M. X.","year":"1996","unstructured":"M. X. Goemans. 1996. Mathematical programming and approximation algorithms. Lecture at the Summer School on Approximate Solution of Hard Combinatorial Problems (1996).","journal-title":"Lecture at the Summer School on Approximate Solution of Hard Combinatorial Problems"},{"key":"e_1_3_2_99_2","doi-asserted-by":"publisher","DOI":"10.5555\/894477"},{"key":"e_1_3_2_100_2","article-title":"The dense k subgraph problem","volume":"0912","author":"Goldstein D.","year":"2009","unstructured":"D. Goldstein and M. Langberg. 2009. The dense k subgraph problem. CoRR abs\/0912.5327.","journal-title":"CoRR"},{"key":"e_1_3_2_101_2","first-page":"116","volume-title":"Proceedings of the 8th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS\u201919)","author":"Gonzales S.","year":"2019","unstructured":"S. Gonzales and T. Migler. 2019. The densest k subgraph problem in b-outerplanar graphs. In Proceedings of the 8th International Conference on Complex Networks and Their Applications (COMPLEX NETWORKS\u201919). 116\u2013127."},{"key":"e_1_3_2_102_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579273"},{"key":"e_1_3_2_103_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.22034"},{"key":"e_1_3_2_104_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-022-00927-1"},{"key":"e_1_3_2_105_2","volume-title":"Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS\u201922)","author":"Harb E.","year":"2022","unstructured":"E. Harb, K. Quanrud, and C. Chekuri. 2022. Faster and scalable algorithms for densest subgraph and decomposition. In Proceedings of the 36th Conference on Neural Information Processing Systems (NeurIPS\u201922)."},{"key":"e_1_3_2_106_2","article-title":"Convergence to lexicographically optimal base in a (contra)polymatroid and applications to densest subgraph and tree packing","author":"Harb E.","year":"2023","unstructured":"E. Harb, K. Quanrud, and C. Chekuri. 2023. Convergence to lexicographically optimal base in a (contra)polymatroid and applications to densest subgraph and tree packing. arXiv:2305.02987. Retrieved from https:\/\/arxiv.org\/abs\/2305.02987","journal-title":"arXiv:2305.02987"},{"key":"e_1_3_2_107_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512205"},{"key":"e_1_3_2_108_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"e_1_3_2_109_2","doi-asserted-by":"publisher","DOI":"10.1137\/090766991"},{"key":"e_1_3_2_110_2","first-page":"65:1\u201365:14","volume-title":"Proceedings of the 30th Annual European Symposium on Algorithms (ESA\u201922)","author":"Henzinger M.","year":"2022","unstructured":"M. Henzinger, A. Paz, and A. R. Sricharan. 2022. Fine-grained complexity lower bounds for families of dynamic graphs. In Proceedings of the 30th Annual European Symposium on Algorithms (ESA\u201922). 65:1\u201365:14."},{"key":"e_1_3_2_111_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0524"},{"key":"e_1_3_2_112_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939747"},{"issue":"1","key":"e_1_3_2_113_2","first-page":"i213\u2013i221","article-title":"Mining coherent dense subgraphs across massive biological networks for functional discovery","volume":"21","author":"Hu H.","year":"2005","unstructured":"H. Hu, X. Yan, Y. Huang, J. Han, and X. J. Zhou. 2005. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics 21, 1 (2005), i213\u2013i221.","journal-title":"Bioinformatics"},{"key":"e_1_3_2_114_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_2_115_2","doi-asserted-by":"publisher","DOI":"10.1109\/EDTC.1995.470419"},{"key":"e_1_3_2_116_2","article-title":"Densest subhypergraph: Negative supermodular functions and strongly localized methods","author":"Huang Y.","year":"2023","unstructured":"Y. Huang, D.F. Gleich, and N. Veldt. 2023. Densest subhypergraph: Negative supermodular functions and strongly localized methods. arXiv:2310.13792. Retrieved from https:\/\/arxiv.org\/abs\/2310.13792","journal-title":"arXiv:2310.13792"},{"key":"e_1_3_2_117_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_3_2_118_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_3_2_119_2","volume-title":"An Introduction to Parallel Algorithms","author":"J\u00e9J\u00e9 J.","year":"1992","unstructured":"J. J\u00e9J\u00e9. 1992. An Introduction to Parallel Algorithms. Addison-Wesley."},{"key":"e_1_3_2_120_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-23525-7_39"},{"key":"e_1_3_2_121_2","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539252"},{"key":"e_1_3_2_122_2","doi-asserted-by":"publisher","DOI":"10.14778\/3570690.3570696"},{"key":"e_1_3_2_123_2","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_2_124_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17656-3_7"},{"key":"e_1_3_2_125_2","volume-title":"Analyzing the Structure of Large Graphs.","author":"Kannan R.","year":"1999","unstructured":"R. Kannan and V. Vinay. 1999. Analyzing the Structure of Large Graphs.Technical Report. Institut f\u00fcr \u00d6konometrie und Operations Research, Universit\u00e4t Bonn."},{"key":"e_1_3_2_126_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2019\/177"},{"key":"e_1_3_2_127_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0400-7"},{"key":"e_1_3_2_128_2","doi-asserted-by":"publisher","DOI":"10.1145\/3539597.3570444"},{"key":"e_1_3_2_129_2","first-page":"27:1\u201327:18","volume-title":"Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201920)","author":"Khanna Y.","year":"2020","unstructured":"Y. Khanna and A. Louis. 2020. Planted models for the densest k-subgraph problem. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS\u201920). 27:1\u201327:18."},{"key":"e_1_3_2_130_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"e_1_3_2_131_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_3_2_132_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380603"},{"key":"e_1_3_2_133_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976007.2"},{"key":"e_1_3_2_134_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.04.029"},{"key":"e_1_3_2_135_2","doi-asserted-by":"publisher","DOI":"10.1145\/3437963.3441756"},{"key":"e_1_3_2_136_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i4.20325"},{"key":"e_1_3_2_137_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1032"},{"issue":"34","key":"e_1_3_2_138_2","first-page":"1","article-title":"A guide to conquer the biological network era using graph theory","volume":"8","author":"Koutrouli M.","year":"2020","unstructured":"M. Koutrouli, E. Karatzas, D. Paez-Espino, and G.A. Pavlopoulos. 2020. A guide to conquer the biological network era using graph theory. Front. Bioeng. Biotechnol. 8, 34 (2020), 1\u201334.","journal-title":"Front. Bioeng. Biotechnol."},{"key":"e_1_3_2_139_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2015.07.008"},{"key":"e_1_3_2_140_2","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525450"},{"key":"e_1_3_2_141_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9554-x"},{"key":"e_1_3_2_142_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403383"},{"key":"e_1_3_2_143_2","first-page":"1","article-title":"Contrast subgraphs allow comparing homogeneous and heterogeneous networks derived from omics data","volume":"12","author":"Lanciano T.","year":"2023","unstructured":"T. Lanciano, A. Savino, F. Porcu, D. Cittaro, F. Bonchi, and P. Provero. 2023. Contrast subgraphs allow comparing homogeneous and heterogeneous networks derived from omics data. GigaScience 12 (2023), 1\u201310.","journal-title":"GigaScience"},{"key":"e_1_3_2_144_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_3_2_145_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.68"},{"issue":"451","key":"e_1_3_2_146_2","article-title":"Densest subgraph-based methods for protein-protein interaction hot spot prediction","volume":"23","author":"Li R.","year":"2022","unstructured":"R. Li, J.Y. Lee, J. M. Yang, and T. Akutsu. 2022. Densest subgraph-based methods for protein-protein interaction hot spot prediction. BMC Bioinf. 23, 451 (2022).","journal-title":"BMC Bioinf."},{"key":"e_1_3_2_147_2","unstructured":"R. Li and K. Quanrud. 2023. Approximate Fully Dynamic Directed Densest Subgraph. arxiv:2312.07827 [cs.DS]. Retrieved from https:\/\/arxiv.org\/abs\/2312.07827"},{"key":"e_1_3_2_148_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i04.5906"},{"key":"e_1_3_2_149_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.03.016"},{"issue":"7","key":"e_1_3_2_150_2","first-page":"3082","article-title":"A stochastic approach to finding densest temporal subgraphs in dynamic graphs","volume":"34","author":"Liu X.","year":"2022","unstructured":"X. Liu, T. Ge, and Y. Wu. 2022. A stochastic approach to finding densest temporal subgraphs in dynamic graphs. IEEE Trans. Knowl. Data Eng. 34, 7 (2022), 3082\u20133094.","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"e_1_3_2_151_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00029"},{"key":"e_1_3_2_152_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561069"},{"key":"e_1_3_2_153_2","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_3_2_154_2","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517837"},{"key":"e_1_3_2_155_2","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_3_2_156_2","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_3_2_157_2","doi-asserted-by":"publisher","DOI":"10.1145\/3483940"},{"key":"e_1_3_2_158_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2891604"},{"key":"e_1_3_2_159_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02993903"},{"key":"e_1_3_2_160_2","doi-asserted-by":"publisher","DOI":"10.3233\/JHS-200635"},{"key":"e_1_3_2_161_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0604-1"},{"key":"e_1_3_2_162_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_3_2_163_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2013.08.002"},{"key":"e_1_3_2_164_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055412"},{"key":"e_1_3_2_165_2","article-title":"Network based approach to gene prioritization at genome-wide association study loci","volume":"2210","author":"Martini L.","year":"2022","unstructured":"L. Martini, A. Fazzone, M. Gentili, L. Becchetti, and B. Hobbs. 2022. Network based approach to gene prioritization at genome-wide association study loci. CoRR abs\/2210.16292.","journal-title":"CoRR"},{"key":"e_1_3_2_166_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48054-0_39"},{"key":"e_1_3_2_167_2","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783385"},{"key":"e_1_3_2_168_2","doi-asserted-by":"publisher","DOI":"10.1145\/3580305.3599306"},{"key":"e_1_3_2_169_2","first-page":"1395","volume-title":"Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915)","author":"Miyauchi A.","year":"2015","unstructured":"A. Miyauchi, Y. Iwamasa, T. Fukunaga, and N. Kakimura. 2015. Threshold influence model for allocating advertising budgets. In Proceedings of the 32nd International Conference on Machine Learning (ICML\u201915). 1395\u20131404."},{"key":"e_1_3_2_170_2","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271720"},{"key":"e_1_3_2_171_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2018.00157"},{"key":"e_1_3_2_172_2","first-page":"23:1\u201323:18","volume-title":"Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC\u201922)","author":"Mizutani Y.","year":"2022","unstructured":"Y. Mizutani and B. D. Sullivan. 2022. Parameterized complexity of maximum happy set and densest k-subgraph. In Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC\u201922). 23:1\u201323:18."},{"key":"e_1_3_2_173_2","doi-asserted-by":"publisher","DOI":"10.1162\/tacl_a_00179"},{"key":"e_1_3_2_174_2","first-page":"977","volume-title":"Proceedings of the 28th International Conference on Machine Learning (ICML\u201911)","author":"Nagano K.","year":"2011","unstructured":"K. Nagano, Y. Kawahara, and K. Aihara. 2011. Size-constrained submodular minimization through minimum norm base. In Proceedings of the 28th International Conference on Machine Learning (ICML\u201911). 977\u2013984."},{"key":"e_1_3_2_175_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.08.012"},{"key":"e_1_3_2_176_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0189-2"},{"key":"e_1_3_2_177_2","first-page":"1890","volume-title":"Proceedings of the 31st International Conference on Machine Learning (ICML\u201914)","author":"Papailiopoulos D.","year":"2014","unstructured":"D. Papailiopoulos, I. Mitliagkas, A. Dimakis, and C. Caramanis. 2014. Finding dense subgraphs via low-rank bilinear optimization. In Proceedings of the 31st International Conference on Machine Learning (ICML\u201914). 1890\u20131898."},{"key":"e_1_3_2_178_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_179_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120206"},{"key":"e_1_3_2_180_2","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920967"},{"key":"e_1_3_2_181_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2022.3233788"},{"key":"e_1_3_2_182_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_183_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488482"},{"key":"e_1_3_2_184_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_3_2_185_2","volume-title":"Finding the Densest Common Subgraph with Linear Programming","author":"Reinthal A.","year":"2016","unstructured":"A. Reinthal, A. T\u00f6rnqvist, A. Andersson, E. Norlander, P. St\u00e5lhammar, and S. Norlin. 2016. Finding the Densest Common Subgraph with Linear Programming. B.S. thesis. Chalmers University of Technology & University of Gothenburg."},{"key":"e_1_3_2_186_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00197"},{"key":"e_1_3_2_187_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623674"},{"key":"e_1_3_2_188_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-019-01403-9"},{"key":"e_1_3_2_189_2","first-page":"20","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201920)","author":"Rozenshtein P.","year":"2020","unstructured":"P. Rozenshtein, G. Preti, A. Gionis, and Y. Velegrakis. 2020. Mining dense subgraphs with similar edges. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201920). 20\u201336."},{"key":"e_1_3_2_190_2","doi-asserted-by":"publisher","DOI":"10.1145\/3046791"},{"key":"e_1_3_2_191_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00115"},{"key":"e_1_3_2_192_2","doi-asserted-by":"crossref","unstructured":"C. Ma. 2019. Supplementary note for \u201cefficient algorithms for densest subgraph discovery on large directed graphs\u201d. https:\/\/i.cs.hku.hk\/%7Echma2\/sup-sigmod2020.pdf","DOI":"10.1145\/3318464.3389697"},{"key":"e_1_3_2_193_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12683-3_30"},{"key":"e_1_3_2_194_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_3_2_195_2","doi-asserted-by":"publisher","DOI":"10.1145\/3057742"},{"key":"e_1_3_2_196_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_3_2_197_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384327"},{"key":"e_1_3_2_198_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"e_1_3_2_199_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_3_2_200_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0602-x"},{"key":"e_1_3_2_201_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-8588-9_10"},{"key":"e_1_3_2_202_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976830.13"},{"key":"e_1_3_2_203_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46128-1_17"},{"key":"e_1_3_2_204_2","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018676"},{"key":"e_1_3_2_205_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098087"},{"key":"e_1_3_2_206_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2019.1595620"},{"key":"e_1_3_2_207_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_3_2_208_2","first-page":"15:1\u201315:18","volume-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC\u201920)","author":"Su H. H.","year":"2020","unstructured":"H. H. Su and H. T. Vu. 2020. Distributed dense subgraph detection and low outdegree orientation. In Proceedings of the 34th International Symposium on Distributed Computing (DISC\u201920). 15:1\u201315:18."},{"key":"e_1_3_2_209_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2023.01.061"},{"key":"e_1_3_2_210_2","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_3_2_211_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449976"},{"key":"e_1_3_2_212_2","first-page":"41:1\u201341:20","volume-title":"Proceedings of the 35th International Symposium on Distributed Computing (DISC\u201921)","author":"Sundaram R. G.","year":"2021","unstructured":"R. G. Sundaram, H. Gupta, and C. R. Ramakrishnan. 2021. Efficient distribution of quantum circuits. In Proceedings of the 35th International Symposium on Distributed Computing (DISC\u201921). 41:1\u201341:20."},{"key":"e_1_3_2_213_2","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963491"},{"key":"e_1_3_2_214_2","doi-asserted-by":"publisher","DOI":"10.1145\/3377811.3380920"},{"key":"e_1_3_2_215_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_216_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_2_217_2","first-page":"378","volume-title":"Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201919)","author":"Tsourakakis C. E.","year":"2019","unstructured":"C. E. Tsourakakis, T. Chen, N. Kakimura, and J. Pachocki. 2019. Novel dense subgraph discovery primitives: Risk aversion and exclusion queries. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD\u201919). 378\u2013394."},{"key":"e_1_3_2_218_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467398"},{"key":"e_1_3_2_219_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1321048"},{"key":"e_1_3_2_220_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2014.09.064"},{"key":"e_1_3_2_221_2","doi-asserted-by":"publisher","DOI":"10.1111\/biom.13537"},{"key":"e_1_3_2_222_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2015.7113344"},{"key":"e_1_3_2_223_2","doi-asserted-by":"publisher","DOI":"10.1145\/2785970"},{"key":"e_1_3_2_224_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15985-5_11"},{"key":"e_1_3_2_225_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICCCN52240.2021.9522263"},{"key":"e_1_3_2_226_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21764"},{"key":"e_1_3_2_227_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00029"},{"key":"e_1_3_2_228_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021390231133"},{"key":"e_1_3_2_229_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313403"},{"key":"e_1_3_2_230_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.10.018"},{"key":"e_1_3_2_231_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-20350-3_25"},{"key":"e_1_3_2_232_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-022-2431-z"},{"key":"e_1_3_2_233_2","volume-title":"Proceedings of the 11th Workshop on Mining and Learning with Graphs (MLG\u201913)","author":"Zou Z.","year":"2013","unstructured":"Z. Zou. 2013. Polynomial-time algorithm for finding densest subgraphs in uncertain graphs. In Proceedings of the 11th Workshop on Mining and Learning with Graphs (MLG\u201913)."}],"container-title":["ACM Computing Surveys"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653298","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3653298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:43Z","timestamp":1750294663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3653298"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4,30]]},"references-count":232,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1145\/3653298"],"URL":"https:\/\/doi.org\/10.1145\/3653298","relation":{},"ISSN":["0360-0300","1557-7341"],"issn-type":[{"value":"0360-0300","type":"print"},{"value":"1557-7341","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,4,30]]},"assertion":[{"value":"2023-03-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-03-07","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-30","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}