{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,26]],"date-time":"2026-07-26T08:14:56Z","timestamp":1785053696939,"version":"3.55.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>Community search aims at finding densely connected subgraphs for query vertices in a graph. While this task has been studied widely in the literature, most of the existing works only focus on finding homogeneous communities rather than heterogeneous communities with different labels. In this paper, we motivate a new problem of cross-group community search, namely Butterfly-Core Community (BCC), over a labeled graph, where each vertex has a label indicating its properties and an edge between two vertices indicates their cross relationship. Specifically, for two query vertices with different labels, we aim to find a densely connected cross community that contains two query vertices and consists of butterfly networks, where each wing of the butterflies is induced by a k-core search based on one query vertex and two wings are connected by these butterflies. We first develop a heuristic algorithm achieving 2-approximation to the optimal solution. Furthermore, we design fast techniques of query distance computations, leader pair identifications, and index-based BCC local explorations. Extensive experiments on seven real datasets and four useful case studies validate the effectiveness and efficiency of our BCC and its multi-labeled extension models.<\/jats:p>","DOI":"10.14778\/3476249.3476258","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2006-2018","source":"Crossref","is-referenced-by-count":50,"title":["Butterfly-core community search over labeled graphs"],"prefix":"10.14778","volume":"14","author":[{"given":"Zheng","family":"Dong","sequence":"first","affiliation":[{"name":"Baidu Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xin","family":"Huang","sequence":"additional","affiliation":[{"name":"Hong Kong Baptist University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guorui","family":"Yuan","sequence":"additional","affiliation":[{"name":"Baidu Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hengshu","family":"Zhu","sequence":"additional","affiliation":[{"name":"Baidu Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hui","family":"Xiong","sequence":"additional","affiliation":[{"name":"Rutgers University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"https:\/\/raw.githubusercontent.com\/jpatokal\/openflights\/master\/data\/routes.dat. https:\/\/raw.githubusercontent.com\/jpatokal\/openflights\/master\/data\/routes.dat."},{"key":"e_1_2_1_2_1","unstructured":"https:\/\/wits.worldbank.org\/datadownload.aspx?lang=en. https:\/\/wits.worldbank.org\/datadownload.aspx?lang=en."},{"key":"e_1_2_1_3_1","unstructured":"https:\/\/github.com\/efekarakus\/potter-network. https:\/\/github.com\/efekarakus\/potter-network."},{"key":"e_1_2_1_4_1","unstructured":"https:\/\/www.aminer.cn\/citation. https:\/\/www.aminer.cn\/citation."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407812"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-015-0422-1"},{"key":"e_1_2_1_7_1","volume-title":"arXiv preprint cs\/0310049","author":"Batagelj Vladimir","year":"2003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3213880.3213881"},{"key":"e_1_2_1_9_1","volume-title":"Network analysis of 2-mode data. Social networks 19, 3","author":"Borgatti Stephen P","year":"1997"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/nws.2015.9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Lu Chen Chengfei Liu Kewen Liao Jianxin Li and Rui Zhou. 2019. Contextual community search over large social networks. In ICDE. 88--99. Lu Chen Chengfei Liu Kewen Liao Jianxin Li and Rui Zhou. 2019. Contextual community search over large social networks. In ICDE. 88--99.","DOI":"10.1109\/ICDE.2019.00017"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3231751.3231755"},{"key":"e_1_2_1_13_1","volume-title":"Jeffrey Xu Yu, and Jianxin Li","author":"Chen Lu","year":"2020"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3358009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476258"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994538"},{"key":"e_1_2_1_20_1","volume-title":"A survey of community search over big graphs. VLDBJ","author":"Fang Yixiang","year":"2019"},{"key":"e_1_2_1_21_1","first-page":"2093","article-title":"Effective and efficient community search over large directed graphs","volume":"31","author":"Fang Yixiang","year":"2018","journal-title":"TKDE"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3380750.3380756"},{"key":"e_1_2_1_23_1","volume-title":"Multi-attributed Community Search in Road-social Networks. arXiv preprint arXiv:2101.09668","author":"Guo Fangda","year":"2021"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3099622.3099626"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3365087"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/3401960.3401969"},{"key":"e_1_2_1_28_1","volume-title":"Vizcs: Online searching and visualizing communities in dynamic graphs","author":"Jiang Yuli","year":"2018"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380603"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368300"},{"key":"e_1_2_1_31_1","unstructured":"Jianxin Li Xinjue Wang Ke Deng Xiaochun Yang Timos Sellis and Jeffrey Xu Yu. 2017. Most influential community search over large social networks. In ICDE. 871--882. Jianxin Li Xinjue Wang Ke Deng Xiaochun Yang Timos Sellis and Jeffrey Xu Yu. 2017. Most influential community search over large social networks. In ICDE. 871--882."},{"key":"e_1_2_1_32_1","volume-title":"Approximately Counting Butterflies in Large Bipartite Graph Streams. TKDE","author":"Li Rundong","year":"2021"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.14778\/3446095.3446099"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380587"},{"key":"e_1_2_1_36_1","volume-title":"VAC: Vertex-Centric Attributed Community Search. In ICDE. 937--948.","author":"Liu Qing","year":"2020"},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Jiehuan Luo Xin Cao Xike Xie Qiang Qu Zhiqiang Xu and Christian S Jensen. 2020. Efficient Attribute-Constrained Co-Located Community Search. In ICDE. 1201--1212. Jiehuan Luo Xin Cao Xike Xie Qiang Qu Zhiqiang Xu and Christian S Jensen. 2020. Efficient Attribute-Constrained Co-Located Community Search. In ICDE. 1201--1212.","DOI":"10.1109\/ICDE48307.2020.00108"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3210025"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:CMOT.0000032580.12184.c0"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220097"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357983"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159678"},{"key":"e_1_2_1_43_1","volume-title":"Network structure and minimum degree. Social networks 5, 3","author":"Seidman Stephen B","year":"1983"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Longxu Sun Xin Huang Rong-Hua Li and Jianliang Xu. 2019. Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. In WISE. 728--744. Longxu Sun Xin Huang Rong-Hua Li and Jianliang Xu. 2019. Fast Algorithms for Intimate-Core Group Search in Weighted Graphs. In WISE. 728--744.","DOI":"10.1007\/978-3-030-34223-4_46"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2481244.2481248"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330849"},{"key":"e_1_2_1_48_1","volume-title":"Market-oriented job skill valuation with cooperative composition neural network. Nature communications 12, 1","author":"Sun Ying","year":"2021"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.3301758"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339497"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Kai Wang Xuemin Lin Lu Qin Wenjie Zhang and Ying Zhang. 2020. Efficient bitruss decomposition for large-scale bipartite graphs. In ICDE. 661--672. Kai Wang Xuemin Lin Lu Qin Wenjie Zhang and Ying Zhang. 2020. Efficient bitruss decomposition for large-scale bipartite graphs. In ICDE. 661--672.","DOI":"10.1109\/ICDE48307.2020.00063"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447702"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.14778\/3457390.3457407"},{"key":"e_1_2_1_56_1","volume-title":"Identifying high potential talent: A neural network based dynamic social profiling approach","author":"Ye Yuyang"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2783933"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Zhiwei Zhang Xin Huang Jianliang Xu Byron Choi and Zechao Shang. 2019. Keyword-Centric Community Search. In ICDE. 422--433. Zhiwei Zhang Xin Huang Jianliang Xu Byron Choi and Zechao Shang. 2019. Keyword-Centric Community Search. In ICDE. 422--433.","DOI":"10.1109\/ICDE.2019.00045"},{"key":"e_1_2_1_59_1","doi-asserted-by":"crossref","unstructured":"Dong Zheng Jianquan Liu Rong-Hua Li Cigdem Aslay Yi-Cheng Chen and Xin Huang. 2017. Querying intimate-core groups in weighted graphs. In ICSC. 156--163. Dong Zheng Jianquan Liu Rong-Hua Li Cigdem Aslay Yi-Cheng Chen and Xin Huang. 2017. Querying intimate-core groups in weighted graphs. In ICSC. 156--163.","DOI":"10.1109\/ICSC.2017.80"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476258","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T22:15:32Z","timestamp":1726006532000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476258"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":60,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476258"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476258","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}