Efficient size-prescribed $k$-core search
<|reference_start|>Efficient size-prescribed $k$-core search: $k$-core is a subgraph where every node has at least $k$ neighbors within the subgraph. The $k$-core subgraphs has been employed in large platforms like Network Repository to comprehend the underlying structures and dynamics of the network. Existing studies have primarily focused on finding $k$-core groups without considering their size, despite the relevance of solution sizes in many real-world scenarios. This paper addresses this gap by introducing the size-prescribed $k$-core search (SPCS) problem, where the goal is to find a subgraph of a specified size that has the highest possible core number. We propose two algorithms, namely the {\it TSizeKcore-BU} and the {\it TSizeKcore-TD}, to identify cohesive subgraphs that satisfy both the $k$-core requirement and the size constraint. Our experimental results demonstrate the superiority of our approach in terms of solution quality and efficiency. The {\it TSizeKcore-BU} algorithm proves to be highly efficient in finding size-prescribed $k$-core subgraphs on large datasets, making it a favorable choice for such scenarios. On the other hand, the {\it TSizeKcore-TD} algorithm is better suited for small datasets where running time is less critical.<|reference_end|>
@article{liu2024efficient,
    title={Efficient size-prescribed $k$-core search},
    author={Yiping Liu, Bo Yan, Bo Zhao, Hongyi Su, Yang Chen, Michael Witbrock},
    journal={arXiv preprint arXiv:2403.09214},
    year={2024},
    doi={10.1145/3625007.3627316},
    archivePrefix={arXiv},
    eprint={2403.09214},
    primaryClass={cs.DS}
}