{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,13]],"date-time":"2026-08-13T16:37:34Z","timestamp":1786639054394,"version":"build-2736575974"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,12]]},"abstract":"Recently, there has been significant interest in the study of the community search problem in social and information networks: given one or more query nodes, find densely connected communities containing the query nodes. However, most existing studies do not address the \"free rider\" issue, that is, nodes far away from query nodes and irrelevant to them are included in the detected community. Some state-of-the-art models have attempted to address this issue, but not only are their formulated problems NP-hard, they do not admit any approximations without restrictive assumptions, which may not always hold in practice.<\/jats:p>\n \n In this paper, given an undirected graph\n G<\/jats:italic>\n and a set of query nodes\n Q<\/jats:italic>\n , we study community search using the\n k<\/jats:italic>\n -truss based community model. We formulate our problem of finding a\n closest truss community<\/jats:italic>\n (CTC), as finding a connected\n k<\/jats:italic>\n -truss subgraph with the largest\n k<\/jats:italic>\n that contains\n Q<\/jats:italic>\n , and has the minimum diameter among such subgraphs. We prove this problem is NP-hard. Furthermore, it is NP-hard to approximate the problem within a factor (2-\u03b5), for any \u03b5 > 0. However, we develop a greedy algorithmic framework, which first finds a CTC containing\n Q<\/jats:italic>\n , and then iteratively removes the furthest nodes from\n Q<\/jats:italic>\n , from the graph. The method achieves 2-approximation to the optimal solution. To further improve the efficiency, we make use of a compact truss index and develop efficient algorithms for\n k<\/jats:italic>\n -truss identification and maintenance as nodes get eliminated. In addition, using bulk deletion optimization and local exploration strategies, we propose two more efficient algorithms. One of them trades some approximation quality for efficiency while the other is a very efficient heuristic. Extensive experiments on 6 real-world networks show the effectiveness and efficiency of our community model and search algorithms.\n <\/jats:p>","DOI":"10.14778\/2856318.2856323","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"276-287","source":"Crossref","is-referenced-by-count":191,"title":["Approximate closest community search in networks"],"prefix":"10.14778","volume":"9","author":[{"given":"Xin","family":"Huang","sequence":"first","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Laks V. S.","family":"Lakshmanan","sequence":"additional","affiliation":[{"name":"University of British Columbia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hong","family":"Cheng","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature09182"},{"key":"e_1_2_1_2_1","unstructured":"V. Batagelj and M. Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 2003. V. Batagelj and M. Zaversnik. An o (m) algorithm for cores decomposition of networks. arXiv preprint cs\/0310049 2003."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/362342.362367"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767911"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_2_1_6_1","volume-title":"National Security Agency","author":"Cohen J.","year":"2008"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSE.2009.120"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463722"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612179"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/645900.672604"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_10"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46648-7_10"},{"key":"e_1_2_1_13_1","volume-title":"Freeman","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875499"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610495"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"X. Huang L. V. Lakshmanan J. X. Yu and H. Cheng. Approximate closest community search in networks. arXiv:1505.05956 2015. X. Huang L. V. Lakshmanan J. X. Yu and H. Cheng. Approximate closest community search in networks. arXiv:1505.05956 2015.","DOI":"10.14778\/2856318.2856323"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288961"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735484"},{"key":"e_1_2_1_20_1","first-page":"548","volume-title":"NIPS","volume":"272","author":"McAuley J. J.","year":"2012"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90066-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"M. E. Newman. Fast algorithm for detecting community structure in networks. Physical review E 69(6):066133 2004. M. E. Newman. Fast algorithm for detecting community structure in networks. Physical review E 69(6):066133 2004.","DOI":"10.1103\/PhysRevE.69.066133"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature03607"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0706851105"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835923"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311909"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2752939.2752948"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.138"},{"key":"e_1_2_1_30_1","first-page":"1079","volume-title":"NIPS","author":"Yang Z.","year":"2012"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2856318.2856323","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:22:37Z","timestamp":1672222957000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2856318.2856323"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.14778\/2856318.2856323"],"URL":"https:\/\/doi.org\/10.14778\/2856318.2856323","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}