{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:37Z","timestamp":1779174817244,"version":"3.51.4"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,5,10]],"date-time":"2024-05-10T00:00:00Z","timestamp":1715299200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSFC Grants","award":["62072034"],"award-info":[{"award-number":["62072034"]}]},{"DOI":"10.13039\/501100006374","name":"National Key Research and Development Program of China","doi-asserted-by":"publisher","award":["2020AAA0108503"],"award-info":[{"award-number":["2020AAA0108503"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100009193","name":"Marsden Fund","doi-asserted-by":"crossref","award":["UOA1732"],"award-info":[{"award-number":["UOA1732"]}],"id":[{"id":"10.13039\/501100009193","id-type":"DOI","asserted-by":"crossref"}]},{"name":"MBIE Catalyst: Strategic Fund NZ-Singapore Data Science Research Programme","award":["UOAX2001"],"award-info":[{"award-number":["UOAX2001"]}]},{"name":"NSFC Grants","award":["U2241211"],"award-info":[{"award-number":["U2241211"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,10]]},"abstract":"<jats:p>\n            Local community search (LCS) finds a community in a given graph G local to a set R of seed nodes by optimizing an objective function. The objective function f(S) for an induced subgraph S encodes the set inclusion criteria of R to a classic community measurement of S such as the conductance and the density. An ideal algorithm for optimizing f(S) is strongly local, that is, the complexity is dependent on R as opposed to G. This paper formulates a general form of objective functions for LCS using configurations and then focuses on a set C of density-based configurations, each corresponding to a density-based LCS objective function. The paper has two main results. i) A constructive classification of C: a configuration in C has a strongly local algorithm for optimizing its corresponding objective function if and only if it is in C\n            <jats:sub>L<\/jats:sub>\n            \u2286 C. ii) A linear programming-based general solution for density-based LCS that is strongly local and practically efficient. This solution is different from the existing strongly local LCS algorithms, which are all based on flow networks.\n          <\/jats:p>","DOI":"10.1145\/3651589","type":"journal-article","created":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T08:32:13Z","timestamp":1715675533000},"page":"1-25","source":"Crossref","is-referenced-by-count":5,"title":["On Density-based Local Community Search"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3662-3520","authenticated-orcid":false,"given":"Yizhou","family":"Dai","sequence":"first","affiliation":[{"name":"The University of Auckland, Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8374-140X","authenticated-orcid":false,"given":"Miao","family":"Qiao","sequence":"additional","affiliation":[{"name":"The University of Auckland, Auckland, New Zealand"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,5,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517890"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3038912.3052619"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565843"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-022-01716--7"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623621"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403069"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/3551793.3551826"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.94"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783299"},{"key":"e_1_2_1_11_1","volume-title":"Proc. of KDD'10","author":"Sozio M.","unstructured":"M. Sozio and A. Gionis. 2010. The community-search problem and how to plan a successful cocktail party. In Proc. of KDD'10. 939--948."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487645"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403222"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19--24, 2016 (JMLR Workshop and Conference Proceedings","volume":"1947","author":"Veldt Nate","unstructured":"Nate Veldt, David F. Gleich, and Michael W. Mahoney. 2016. A Simple and Strongly-Local Flow-Based Method for Cut Improvement. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19--24, 2016 (JMLR Workshop and Conference Proceedings, Vol. 48), Maria-Florina Balcan and Kilian Q. Weinberger (Eds.). JMLR.org, 1938--1947. http:\/\/proceedings.mlr.press\/v48\/veldt16.html"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975673.43"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651589","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3651589","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T21:38:55Z","timestamp":1755898735000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3651589"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,10]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,5,10]]}},"alternative-id":["10.1145\/3651589"],"URL":"https:\/\/doi.org\/10.1145\/3651589","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,10]]}}}