{"ID":22918773,"CreatedAt":"2026-09-17T01:02:08.507062015Z","UpdatedAt":"2026-09-20T18:11:56.143995915Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2609.17822","arxiv_id":"2609.17822","title":"Improved Methods for k-core Community Search","abstract":"Community search based on user-specified query nodes is complementary to community finding or graph clustering. Prior work in community search is divided into optimizing for external separate- ness or internal cohesiveness, which does not scale well networks of over a billion edges. We present SteinerKCore, a new scalable k-core based community search algorithm for multi-vertex queries. We also present Par-ShellStruct, a parallel algorithm for building the ShellStruct data structure used for k-core community search. We show that our implemen- tations in Icebug, an open-source toolkit for large-scale network analysis, are both more efficient and more scalable than comparative tools, being able to perform on a benchmark network of 273M and 5.1B edges using just 64GB RAM and under 4 hours runtime with 16 CPUs.","short_abstract":"Community search based on user-specified query nodes is complementary to community finding or graph clustering. Prior work in community search is divided into optimizing for external separate- ness or internal cohesiveness, which does not scale well networks of over a billion edges. We present SteinerKCore, a new scala...","url_abs":"https://arxiv.org/abs/2609.17822","url_pdf":"https://arxiv.org/pdf/2609.17822v1","authors":"[\"Ian Chen\",\"Haotian Yi\",\"Arun Sharma\",\"George Chacko\",\"Tandy Warnow\"]","published":"2026-09-15T20:37:56Z","proceeding":"cs.SI","tasks":"[\"cs.SI\"]","methods":"[]","has_code":false}