{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:58:10Z","timestamp":1781326690061,"version":"3.54.1"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62394333"],"award-info":[{"award-number":["62394333"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["RS-2025-00523578"],"award-info":[{"award-number":["RS-2025-00523578"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,12,4]]},"abstract":"<jats:p>\n                    Community search in heterogeneous graphs is fundamental to applications such as expert team formation and scholarly collaboration. Many existing studies leverage meta-paths, which are sequences of node and edge types, to capture semantic relationships in heterogeneous graphs. However, most of them only consider the existence of meta-path instances, overlooking their frequency and thus failing to capture relationship strength. This limitation can result in communities that include nodes with numerous but weak relations. To capture the strength of relationships in heterogeneous graphs, we define the\n                    <jats:bold>Strong Community<\/jats:bold>\n                    (StrCom) model, which evaluates the strength between users based on the number of connecting meta-path instances. Building upon this model, we further propose the\n                    <jats:bold>Budgeted Strong Community<\/jats:bold>\n                    (BSC) problem by incorporating a size constraint. We provide theoretical analyses showing that the BSC problem is\n                    <jats:bold>NP-hard<\/jats:bold>\n                    and\n                    <jats:bold>not in APX.<\/jats:bold>\n                    To address this problem, we design three strategies-Shrink, Expand, and Hybrid-along with several optimization techniques to improve efficiency. Extensive experiments on large real-world datasets (e.g., DBLP, YAGO, DBpedia) demonstrate the effectiveness and efficiency of our approach. Specifically, our method achieves 3.49-107.09\u00d7 higher PathSim scores for StrCom and two to five orders of magnitude higher scores for BSC compared to state-of-the-art baselines, demonstrating that the identified communities are both semantically coherent and structurally compact.\n                  <\/jats:p>","DOI":"10.1145\/3769768","type":"journal-article","created":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:32:13Z","timestamp":1764995533000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Budgeted Strong Community Search in Heterogeneous Graphs"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0009-0002-6671-894X","authenticated-orcid":false,"given":"Wentong","family":"Zhang","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4196-9366","authenticated-orcid":false,"given":"Kaiyu","family":"Feng","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1374-395X","authenticated-orcid":false,"given":"Lanting","family":"Fang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4905-2704","authenticated-orcid":false,"given":"Junghoon","family":"Kim","sequence":"additional","affiliation":[{"name":"Ulsan National Institute of Science &amp; Technology, Ulsan, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-2832-268X","authenticated-orcid":false,"given":"Kaibo","family":"Zhang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-9239-7396","authenticated-orcid":false,"given":"Dahee","family":"Kim","sequence":"additional","affiliation":[{"name":"Ulsan National Institute of Science &amp; Technology, Ulsan, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5326-7209","authenticated-orcid":false,"given":"Shuliang","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0247-9866","authenticated-orcid":false,"given":"Ye","family":"Yuan","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-93980-1_3"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.DAM.2012.03.025"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.23966"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3627673.3679696"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.1997.612321"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651589"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098036"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1651274.1651278"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00035"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055337"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-019-00556-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-97568-5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00273"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/3282495.3282497"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00189"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00072"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401969"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551795"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2024.120664"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547318"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380603"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368300"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00077"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE51399.2021.00016"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.joi.2022.101372"},{"key":"e_1_2_1_30_1","volume-title":"Data, measurement and empirical methods in the science of science. Nature human behaviour","author":"Liu Lu","year":"2023","unstructured":"Lu Liu, Benjamin F Jones, Brian Uzzi, and Dashun Wang. 2023b. Data, measurement and empirical methods in the science of science. Nature human behaviour, Vol. 7, 7 (2023), 1046-1058."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE60146.2024.00254"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654956"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2021.3131611"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11390-019-1905-0"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2012.08.001"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-73194-6_12"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/S11227-017-1976-Z"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2833443"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2021.3137396"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3040762"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481244.2481248"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402736"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41598-024-51606-6"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.ESWA.2023.121153"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00030"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00083"},{"key":"e_1_2_1_47_1","volume-title":"Juan Ignacio Perotti, and Claudio J. Tessone","author":"Yang Zhao","year":"2017","unstructured":"Zhao Yang, Juan Ignacio Perotti, and Claudio J. Tessone. 2017. Hierarchical benchmark graphs for testing community detection algorithms. CoRR, Vol. abs\/1708.06969 (2017). arXiv:1708.06969 http:\/\/arxiv.org\/abs\/1708.06969"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457407"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.2207436119"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3280483"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2024.3518777"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2017.07.012"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.INS.2023.119511"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594532"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3681954.3681975"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00778-017-0473-610.1007\/S00778-017-0473-6"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3769768","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,13]],"date-time":"2026-06-13T04:43:14Z","timestamp":1781325794000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3769768"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12,4]]},"references-count":56,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,4]]}},"alternative-id":["10.1145\/3769768"],"URL":"https:\/\/doi.org\/10.1145\/3769768","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12,4]]}}}