{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:38Z","timestamp":1750309418913,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,10,21]],"date-time":"2024-10-21T00:00:00Z","timestamp":1729468800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1839317, DMS-2023495"],"award-info":[{"award-number":["CCF-1839317, DMS-2023495"]}],"id":[{"id":"10.13039\/https:\/\/doi.org\/10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,10,21]]},"DOI":"10.1145\/3627673.3679578","type":"proceedings-article","created":{"date-parts":[[2024,10,20]],"date-time":"2024-10-20T19:34:21Z","timestamp":1729452861000},"page":"109-119","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Covering a Graph with Dense Subgraph Families, via Triangle-Rich Sets"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7183-0296","authenticated-orcid":false,"given":"Sabyasachi","family":"Basu","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1073-6173","authenticated-orcid":false,"given":"Daniel","family":"Paul-Pena","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9063-102X","authenticated-orcid":false,"given":"Kun","family":"Qian","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2163-3555","authenticated-orcid":false,"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz & Amazon, Santa Cruz, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4461-8545","authenticated-orcid":false,"given":"Edward W","family":"Huang","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9023-2248","authenticated-orcid":false,"given":"Karthik","family":"Subbian","sequence":"additional","affiliation":[{"name":"Amazon, Palo Alto, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,10,21]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"2024. https:\/\/github.com\/amazon-science\/amazon-RTRExtractor."},{"key":"e_1_3_2_1_2_1","volume-title":"NeurIPS","author":"Alsentzer Emily","year":"2020","unstructured":"Emily Alsentzer, Samuel G. Finlayson, Michelle M. Li, and Marinka Zitnik. 2020. Subgraph Neural Networks. In NeurIPS 2020."},{"key":"e_1_3_2_1_3_1","volume-title":"Alain Barrat, and Alessandro Vespignani.","author":"J.","year":"2005","unstructured":"J. Alvarez-hamelin, Luca Dall' asta, Alain Barrat, and Alessandro Vespignani. 2005. Large scale networks fingerprinting and visualization using the k-core decomposition. In Advances in Neural Information Processing Systems, Vol. 18."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen and Kumar Chellapilla. 2009. Finding Dense Subgraphs with Size Bounds. In Algorithms and Models for the Web-Graph. 25--37.","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_3_2_1_7_1","volume-title":"Machine Learning 56, 1 (01","author":"Bansal Nikhil","year":"2004","unstructured":"Nikhil Bansal, Avrim Blum, and Shuchi Chawla. 2004. Correlation Clustering. Machine Learning 56, 1 (01 Jul 2004), 89--113."},{"key":"e_1_3_2_1_8_1","volume-title":"Suman Kalyan Bera, and C. Seshadhri","author":"Basu Sabyasachi","year":"2024","unstructured":"Sabyasachi Basu, Suman Kalyan Bera, and C. Seshadhri. 2024. Spectral Triadic Decompositions of Real-World Networks. arXiv:2211.06352 [cs.SI]"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1037\/0021-9010.88.6.989"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"A. Benson D. F. Gleich and J. Leskovec. 2016. Higher-order organization of complex networks. Science 353 6295 (2016) 163--166.","DOI":"10.1126\/science.aad9029"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_3_2_1_12_1","volume-title":"Tsourakakis","author":"Bonchi Francesco","year":"2021","unstructured":"Francesco Bonchi, David Garc\u00eda-Soriano, Atsushi Miyauchi, and Charalampos E. Tsourakakis. 2021. Finding densest k-connected subgraphs. Discrete Applied Mathematics 305 (Dec. 2021), 34--47."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Gregory Buehrer and Kumar Chellapilla. 2008. A scalable pattern mining approach to web graph compression with communities (WSDM '08). 95--106.","DOI":"10.1145\/1341531.1341547"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar. 2000. Greedy Approximation Algorithms for Finding Dense Components in a Graph. In Approximation Algorithms for Combinatorial Optimization. 84--95.","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Chandra Chekuri Kent Quanrud and Manuel R. Torres. [n.d.]. Densest Subgraph: Supermodularity Iterative Peeling and Flow. 1531--1555.","DOI":"10.1137\/1.9781611977073.64"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_3_2_1_18_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. In Technical report","author":"Cohen J.","year":"2008","unstructured":"J. Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. In Technical report, National Security Agency."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Maximilien Danisch T.-H. Hubert Chan and Mauro Sozio. 2017. Large Scale Density-friendly Graph Decomposition via Convex Programming (WWW '17). 233--242.","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242635"},{"volume-title":"Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '09)","author":"Du Xiaoxi","key":"e_1_3_2_1_21_1","unstructured":"Xiaoxi Du, Ruoming Jin, Liang Ding, Victor E. Lee, and John H. Thornton. 2009. Migration motif: a spatial - temporal pattern mining approach for financial markets. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD '09). 1135--1144."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Uriel Feige. 2002. Relations between average case complexity and approximation complexity (STOC '02). 534--543.","DOI":"10.1145\/509984.509985"},{"key":"e_1_3_2_1_24_1","unstructured":"D.R. Forsyth. 2010. Group Dynamics. Wadsworth."},{"key":"e_1_3_2_1_25_1","unstructured":"Fabrizio Frasca Beatrice Bevilacqua Michael M. Bronstein and Haggai Maron. 2022. Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries. arXiv:2206.11140 [cs.LG]"},{"key":"e_1_3_2_1_26_1","volume-title":"England) 22, 14","author":"Fratkin Eugene","year":"2006","unstructured":"Eugene Fratkin, Brian T Naughton, Douglas L Brutlag, and Serafim Batzoglou. 2006. MotifCut: regulatory motifs finding with maximum density subgraphs. Bioinformatics (Oxford, England) 22, 14 (2006), e150-7."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083676"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2536336.2536342"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Rishi Gupta Tim Roughgarden and C. Seshadhri. 2014. Decompositions of Triangle-Dense Graphs. Innovations in Theoretical Computer Science (2014) 471--482.","DOI":"10.1145\/2554797.2554840"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392825"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBME.2003.810689"},{"key":"e_1_3_2_1_35_1","volume-title":"A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning","author":"Jin Di","year":"2021","unstructured":"Di Jin, Zhizhi Yu, Pengfei Jiao, Shirui Pan, Dongxiao He, Jia Wu, Philip Yu, and Weixiong Zhang. 2021. A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning. IEEE Transactions on Knowledge and Data Engineering (2021), 1--1."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559930"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence 36","author":"Konar Aritra","year":"2022","unstructured":"Aritra Konar and Nicholas D. Sidiropoulos. 2022. The Triangle-Densest-K-Subgraph Problem: Hardness, Lov\u00e1sz Extension, and Application to Document Summarization. Proceedings of the AAAI Conference on Artificial Intelligence 36, 4 (Jun. 2022), 4075--4082."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(99)00040-7"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Tommaso Lanciano Atsushi Miyauchi Adriano Fazzone and Francesco Bonchi. 2023. A Survey on the Densest Subgraph Problem and its Variants. arXiv:2303.14467 [cs.DS]","DOI":"10.1145\/3653298"},{"volume-title":"A Survey of Algorithms for Dense Subgraph Discovery","author":"Lee Victor E.","key":"e_1_3_2_1_41_1","unstructured":"Victor E. Lee, Ning Ruan, Ruoming Jin, and Charu Aggarwal. 2010. A Survey of Algorithms for Dense Subgraph Discovery. Springer US, 303--336."},{"key":"e_1_3_2_1_42_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"volume-title":"Proceedings of the 17th International Conference on World Wide Web (WWW '08)","author":"Leskovec Jure","key":"e_1_3_2_1_43_1","unstructured":"Jure Leskovec, Kevin J. Lang, Anirban Dasgupta, and Michael W. Mahoney. 2008. Statistical Properties of Community Structure in Large Social and Information Networks. In Proceedings of the 17th International Conference on World Wide Web (WWW '08). 695--704."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Atsushi Miyauchi and Naonori Kakimura. 2018. Finding a Dense Subgraph with Sparse Cut (CIKM '18). 547--556.","DOI":"10.1145\/3269206.3271720"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Atsushi Miyauchi and Yasushi Kawase. 2015. What Is a Network Community? A Novel Quality Function and Detection Algorithms (CIKM '15). 1471--1480.","DOI":"10.1145\/2806416.2806555"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.76.036106"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1140\/epjst\/e2010-01179-1"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","unstructured":"A. Erdem Sariyuce C. Seshadhri A. Pinar and U. Catalyurek. 2015. Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In World Wide Web (WWW). 927--937.","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Venu Satuluri Srinivasan Parthasarathy and Yiye Ruan. [n.d.]. Local graph sparsification for scalable clustering (SIGMOD '11). 721--732.","DOI":"10.1145\/1989323.1989399"},{"key":"e_1_3_2_1_52_1","volume-title":"Anomalies and Algorithms (ICDM '16)","author":"Shin Kijung","year":"2016","unstructured":"Kijung Shin, Tina Eliassi-Rad, and Christos Faloutsos. 2016. CoreScope: Graph Mining Using k-Core Analysis - Patterns, Anomalies and Algorithms (ICDM '16). 469--478."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1080\/10556788.2019.1595620"},{"key":"e_1_3_2_1_54_1","volume-title":"Arnet-Miner: Extraction and Mining of Academic Social Networks. SIGKDD Conference on Knowledge Discovery and Data Mining (KDD)","author":"Tang Jie","year":"2008","unstructured":"Jie Tang, Jing Zhang, Limin Yao, Juanzi Li, Li Zhang, and Zhong Su. 2008. Arnet-Miner: Extraction and Mining of Academic Social Networks. SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) (2008), 990--998."},{"key":"e_1_3_2_1_55_1","volume-title":"From Louvain to","author":"Traag V.A.","year":"2019","unstructured":"V.A. Traag, L. Waltman, and N.J. van Eck. 2019. From Louvain to Leiden: guaranteeing well-connected communities. Scientific Reports 9, 5233 (2019)."},{"key":"e_1_3_2_1_56_1","volume-title":"A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem. CoRR abs\/1405.1477","author":"Tsourakakis Charalampos E.","year":"2014","unstructured":"Charalampos E. Tsourakakis. 2014. A Novel Approach to Finding Near-Cliques: The Triangle-Densest Subgraph Problem. CoRR abs\/1405.1477 (2014)."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_1_58_1","unstructured":"Charalampos E. Tsourakakis Jakub Pachocki and Michael Mitzenmacher. [n.d.]. Scalable Motif-aware Graph Clustering (WWW '17). 1451--1460."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Nate Veldt David F. Gleich and Anthony Wirth. [n.d.]. A Correlation Clustering Framework for Community Detection (WWW '18). 439--448.","DOI":"10.1145\/3178876.3186110"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589314"},{"key":"e_1_3_2_1_63_1","volume-title":"A general framework for weighted gene co-expression network analysis. Statistical applications in genetics and molecular biology 4","author":"Zhang Bin","year":"2005","unstructured":"Bin Zhang and Steve Horvath. 2005. A general framework for weighted gene co-expression network analysis. Statistical applications in genetics and molecular biology 4 (2005), Article17."}],"event":{"name":"CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management","sponsor":["SIGIR ACM Special Interest Group on Information Retrieval"],"location":"Boise ID USA","acronym":"CIKM '24"},"container-title":["Proceedings of the 33rd ACM International Conference on Information and Knowledge Management"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679578","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3627673.3679578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:58:22Z","timestamp":1750294702000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3627673.3679578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10,21]]},"references-count":62,"alternative-id":["10.1145\/3627673.3679578","10.1145\/3627673"],"URL":"https:\/\/doi.org\/10.1145\/3627673.3679578","relation":{},"subject":[],"published":{"date-parts":[[2024,10,21]]},"assertion":[{"value":"2024-10-21","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}