{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:59:47Z","timestamp":1750309187067,"version":"3.41.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,2,12]],"date-time":"2024-02-12T00:00:00Z","timestamp":1707696000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["17203122"],"award-info":[{"award-number":["17203122"]}]},{"name":"French National Agency","award":["ANR-20-CE38-0011"],"award-info":[{"award-number":["ANR-20-CE38-0011"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,5,31]]},"abstract":"<jats:p>\n            Finding dense subgraphs in large (hyper)graphs is a key primitive in a variety of real-world application domains, encompassing social network analytics, event detection, biology, and finance. In most such applications, one typically aims at finding several (possibly overlapping) dense subgraphs, which might correspond to communities in social networks or interesting events. While a large amount of work is devoted to finding a single densest subgraph, perhaps surprisingly, the problem of finding several dense subgraphs in weighted hypergraphs with limited overlap has not been studied in a principled way, to the best of our knowledge. In this work, we define and study a natural generalization of the densest subgraph problem in weighted hypergraphs, where the main goal is to find at most\n            <jats:italic>k<\/jats:italic>\n            subgraphs with maximum total aggregate density, while satisfying an upper bound on the pairwise weighted Jaccard coefficient, i.e., the ratio of weights of intersection divided by weights of union on two nodes sets of the subgraphs. After showing that such a problem is NP-Hard, we devise an efficient algorithm that comes with provable guarantees in some cases of interest, as well as, an efficient practical heuristic. Our extensive evaluation on large real-world hypergraphs confirms the efficiency and effectiveness of our algorithms.\n          <\/jats:p>","DOI":"10.1145\/3639410","type":"journal-article","created":{"date-parts":[[2024,1,2]],"date-time":"2024-01-02T21:58:31Z","timestamp":1704232711000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Finding Subgraphs with Maximum Total Density and Limited Overlap in Weighted Hypergraphs"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1469-3664","authenticated-orcid":false,"given":"Oana","family":"Balalau","sequence":"first","affiliation":[{"name":"Inria and Institut Polytechnique de Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9464-8315","authenticated-orcid":false,"given":"Francesco","family":"Bonchi","sequence":"additional","affiliation":[{"name":"Centai, Turin, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8340-235X","authenticated-orcid":false,"given":"T-H. Hubert","family":"Chan","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, The University of Hong Kong,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7052-1114","authenticated-orcid":false,"given":"Francesco","family":"Gullo","sequence":"additional","affiliation":[{"name":"UniCredit, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2031-3974","authenticated-orcid":false,"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[{"name":"Institut Polytechnique de Paris, Telecom Paris, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-2301-8069","authenticated-orcid":false,"given":"Hao","family":"Xie","sequence":"additional","affiliation":[{"name":"Dept. of Computer Science, The University of Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,12]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-95995-3_3"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.14778\/2168651.2168658"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00243-8"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140442"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2684822.2685298"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1609\/icwsm.v14i1.7347"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3512158"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746592"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623655"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380140"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44436-X_10"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.64"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2010.271"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/16M1096402"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00664-3"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557142"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741638"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl243"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-016-0464-z"},{"key":"e_1_3_2_25_2","volume-title":"Proceedings of the VLDB","author":"Gibson David","year":"2005","unstructured":"David Gibson, Ravi Kumar, and Andrew Tomkins. 2005. Discovering large dense subgraphs in massive graphs. In Proceedings of the VLDB."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.5555\/894477"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132907"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.13"},{"issue":"4","key":"e_1_3_2_29_2","article-title":"Ruling out PTAS for graph min-bisection, dense  \\(k\\) -subgraph, and bipartite clique","volume":"36","author":"Khot Subhash","year":"2006","unstructured":"Subhash Khot. 2006. Ruling out PTAS for graph min-bisection, dense \\(k\\) -subgraph, and bipartite clique. J. Comput. 36, 4 (2006).","journal-title":"J. Comput."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_50"},{"key":"e_1_3_2_31_2","first-page":"743","volume-title":"Proceedings of the WSDM","author":"Konar Aritra","year":"2021","unstructured":"Aritra Konar and Nicholas D. Sidiropoulos. 2021. Exploring the subgraph density-size trade-off via the Lova\u015bz extension. In Proceedings of the WSDM. ACM, 743\u2013751."},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","unstructured":"Tommaso Lanciano Atsushi Miyauchi Adriano Fazzone and Francesco Bonchi. 2023. A survey on the densest subgraph problem and its variants. Retrieved from https:\/\/arXiv:2303.14467. 10.48550\/arXiv.2303.14467","DOI":"10.48550\/arXiv.2303.14467"},{"key":"e_1_3_2_33_2","volume-title":"Methods of Microarray Data Analysis IV","author":"Langston Michael A.","year":"2005","unstructured":"Michael A. Langston and et al.2005. A combinatorial approach to the analysis of differential gene expression data: The use of graph algorithms for disease prediction and screening. In Methods of Microarray Data Analysis IV. Springer, Berlin."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-6045-0_10"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2014.2346173"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/3471485.3471494"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132966"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401962"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40991-2_3"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741119"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_2_46_2","first-page":"378","volume-title":"Proceedings of the ECML\/PKDD (1) (Lecture Notes in Computer Science)","volume":"11906","author":"Tsourakakis Charalampos E.","year":"2019","unstructured":"Charalampos E. Tsourakakis, Tianyi Chen, Naonori Kakimura, and Jakub Pachocki. 2019. Novel dense subgraph discovery primitives: Risk aversion and exclusion queries. In Proceedings of the ECML\/PKDD (1) (Lecture Notes in Computer Science), Vol. 11906. Springer, 378\u2013394."},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31235-9_14"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.14778\/1921071.1921073"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639410","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639410","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:54:11Z","timestamp":1750287251000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639410"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,12]]},"references-count":47,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5,31]]}},"alternative-id":["10.1145\/3639410"],"URL":"https:\/\/doi.org\/10.1145\/3639410","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2024,2,12]]},"assertion":[{"value":"2022-06-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-15","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}