{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T17:42:49Z","timestamp":1757612569367,"version":"3.44.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"10","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:p>\n            To analyze the massive social networks for providing personalized services, community search is widely studied to find the densely connected subgraph that can reflect the network properties for a given query. The existing community search methods adopt single community model to make structural constraints on communities, which can only describe single interaction mode. Since they fail to capture the semantics of the network with multiple interaction modes, they struggle to find the representative communities. To solve this issue, we design a novel community model called (\n            <jats:italic toggle=\"yes\">\u03c4, \u03c1<\/jats:italic>\n            )-camp to flexibly capture complex network semantics in any level of granularity. We propose the unified support maximized community search problem to find the communities with the densest network semantics, which is proven a NP-hard problem. By constructing a hierarchical index structure, we propose an approximate community search algorithm with approximation ratio of 2 and linear time complexity of the query size. Extensive experiments are conducted on two public datasets and two crawled datasets. The experimental results prove the effectiveness and efficiency of our method.\n          <\/jats:p>","DOI":"10.14778\/3748191.3748223","type":"journal-article","created":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:50:16Z","timestamp":1756993816000},"page":"3669-3681","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain"],"prefix":"10.14778","volume":"18","author":[{"given":"Shuai","family":"Han","sequence":"first","affiliation":[{"name":"Harbin Engineering University, Harbin, China"}]},{"given":"Yushi","family":"Tao","sequence":"additional","affiliation":[{"name":"Harbin Engineering University, Harbin, China"}]},{"given":"Jingwen","family":"Tan","sequence":"additional","affiliation":[{"name":"Harbin Engineering University, Harbin, China"}]},{"given":"Huanran","family":"Wang","sequence":"additional","affiliation":[{"name":"Harbin Engineering University, Harbin, China"}]},{"given":"Wu","family":"Yang","sequence":"additional","affiliation":[{"name":"Harbin Engineering University, Harbin, China"}]},{"given":"Yanmei","family":"Wang","sequence":"additional","affiliation":[{"name":"China Unicom (Heilongjiang) Company, Harbin, China"}]}],"member":"320","published-online":{"date-parts":[[2025,9,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137640"},{"key":"e_1_2_1_2_1","volume-title":"2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2699\u20132712","author":"Chen Zi","year":"2023","unstructured":"Zi Chen, Yiwei Zhao, Long Yuan, Xuemin Lin, and Kai Wang. 2023. Index-based biclique percolation communities search on bipartite graphs. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). IEEE, 2699\u20132712."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_4_1","volume-title":"Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1","author":"Cohen Jonathan","year":"2008","unstructured":"Jonathan Cohen. 2008. Trusses: Cohesive subgraphs for social network analysis. National security agency technical report 16, 3.1 (2008)."},{"key":"e_1_2_1_5_1","volume-title":"International Conference on Management of Data, SIGMOD. ACM, 991\u20131002","author":"Cui Wanyun","year":"2014","unstructured":"Wanyun Cui, Yanghua Xiao, Haixun Wang, and Wei Wang. 2014. Local search of communities in large graphs. In International Conference on Management of Data, SIGMOD. ACM, 991\u20131002."},{"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.1007\/978-3-662-04245-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_2_1_9_1","volume-title":"Community detection in complex networks using extremal optimization. Physical Review E\u2014Statistical, Nonlinear, and Soft Matter Physics 72, 2","author":"Duch Jordi","year":"2005","unstructured":"Jordi Duch and Alex Arenas. 2005. Community detection in complex networks using extremal optimization. Physical Review E\u2014Statistical, Nonlinear, and Soft Matter Physics 72, 2 (2005), 027104."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00556-x"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_12_1","volume-title":"Community detection in networks: A user guide. Physics reports 659","author":"Fortunato Santo","year":"2016","unstructured":"Santo Fortunato and Darko Hric. 2016. Community detection in networks: A user guide. Physics reports 659 (2016), 1\u201344."},{"key":"e_1_2_1_13_1","volume-title":"Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997","author":"Gasteiger Johannes","year":"2018","unstructured":"Johannes Gasteiger, Aleksandar Bojchevski, and Stephan G\u00fcnnemann. 2018. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 (2018)."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1137\/1024022","article-title":"Computers and intractability: a guide to the theory of np-completeness","volume":"24","author":"Hartmanis Juris","year":"1982","unstructured":"Juris Hartmanis. 1982. Computers and intractability: a guide to the theory of np-completeness. Siam Review 24, 1 (1982), 90.","journal-title":"Siam Review"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_16_1","volume-title":"2017 IEEE 33rd international conference on data engineering (ICDE). 1451\u20131454","author":"Huang Xin","year":"2017","unstructured":"Xin Huang, Laks VS Lakshmanan, and Jianliang Xu. 2017. Community search over big graphs: Models, algorithms, and opportunities. In 2017 IEEE 33rd international conference on data engineering (ICDE). 1451\u20131454."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551795"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551795"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526137"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"404","DOI":"10.14778\/3430915.3430929","article-title":"RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs","volume":"14","author":"Lakhotia Kartik","year":"2021","unstructured":"Kartik Lakhotia, Rajgopal Kannan, Viktor K. Prasanna, and C\u00e9sar A. F. De Rose. 2021. RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs. Proc. VLDB Endow. 14, 3 (2021), 404\u2013417.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3659437.3659440"},{"key":"e_1_2_1_23_1","volume-title":"Efficient Community Search with Size Constraint. In 37th IEEE International Conference on Data Engineering, ICDE 2021","author":"Liu Boge","year":"2021","unstructured":"Boge Liu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2021. Efficient Community Search with Size Constraint. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19\u201322, 2021. IEEE, 97\u2013108."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00587-4"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3040762"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551834"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3290295"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-021-00658-5"},{"key":"e_1_2_1_32_1","volume-title":"Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. In 38th IEEE International Conference on Data Engineering, ICDE 2022","author":"Wang Kai","year":"2022","unstructured":"Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Shunyang Li. 2022. Discovering Hierarchy of Bipartite Graphs with Cohesive Subgraphs. In 38th IEEE International Conference on Data Engineering, ICDE 2022, Kuala Lumpur, Malaysia, May 9\u201312, 2022. IEEE, 2291\u20132305."},{"key":"e_1_2_1_33_1","volume-title":"2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 85\u201396","author":"Wang Kai","year":"2021","unstructured":"Kai Wang, Wenjie Zhang, Xuemin Lin, Ying Zhang, Lu Qin, and Yuting Zhang. 2021. Efficient and effective community search on large-scale bipartite graphs. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE, 85\u201396."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1691\u20131700","author":"Xie Xiaoqin","year":"2024","unstructured":"Xiaoqin Xie, Shuangyuan Liu, Jiaqi Zhang, Shuai Han, Wei Wang, and Wu Yang. 2024. Efficient Community Search Based on Relaxed k-Truss Index. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval. 1691\u20131700."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-024-00855-y"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2350190.2350193"},{"key":"e_1_2_1_37_1","volume-title":"39th IEEE International Conference on Data Engineering, ICDE 2023","author":"Ye Junhao","year":"2023","unstructured":"Junhao Ye, Yuanyuan Zhu, and Lu Chen. 2023. Top-r keyword-based community search in attributed graphs. In 39th IEEE International Conference on Data Engineering, ICDE 2023, Anaheim, CA, USA, April 3\u20137, 2023. IEEE, 1652\u20131664."},{"key":"e_1_2_1_38_1","volume-title":"Index-Based Densest Clique Percolation Community Search in Networks. In 35th IEEE International Conference on Data Engineering. IEEE, 2161\u20132162","author":"Yuan Long","year":"2019","unstructured":"Long Yuan, Lu Qin, Wenjie Zhang, Lijun Chang, and Jianye Yang. 2019. Index-Based Densest Clique Percolation Community Search in Networks. In 35th IEEE International Conference on Data Engineering. IEEE, 2161\u20132162."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00023"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3280483"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055332"},{"key":"e_1_2_1_42_1","volume-title":"On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15","author":"Zhang Yun","year":"2014","unstructured":"Yun Zhang, Charles A Phillips, Gary L Rogers, Erich J Baker, Elissa J Chesler, and Michael A Langston. 2014. On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types. BMC bioinformatics 15 (2014), 1\u201318."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3594512.3594532"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3748191.3748223","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,4]],"date-time":"2025-09-04T13:54:44Z","timestamp":1756994084000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3748191.3748223"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":43,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["10.14778\/3748191.3748223"],"URL":"https:\/\/doi.org\/10.14778\/3748191.3748223","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"2025-09-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}