Scalable $k$-clique Densest Subgraph Search
<|reference_start|>Scalable $k$-clique Densest Subgraph Search: In this paper, we present a collection of novel and scalable algorithms designed to tackle the challenges inherent in the $k$-clique densest subgraph problem (\kcdsp) within network analysis. We propose \psctl, a novel algorithm based on the Frank-Wolfe approach for addressing \kcdsp, effectively solving a distinct convex programming problem. \textcolor{black}{\psctl is able to approximate \kcdsp with near optimal guarantees.} The notable advantage of \psctl lies in its time complexity, which is independent of the count of $k$-cliques, resulting in remarkable efficiency in practical applications. Additionally, we present \spath, a sampling-based algorithm with the capability to handle networks on an unprecedented scale, reaching up to $1.8\times 10^9$ edges. By leveraging the \ccpath algorithm as a uniform $k$-clique sampler, \spath ensures the efficient processing of large-scale network data, accompanied by a detailed analysis of accuracy guarantees. Together, these contributions represent a significant advancement in the field of $k$-clique densest subgraph discovery. In experimental evaluations, our algorithms demonstrate orders of magnitude faster performance compared to the current state-of-the-art solutions.<|reference_end|>
@article{ye2024scalable,
    title={Scalable $k$-clique Densest Subgraph Search},
    author={Xiaowei Ye, Miao Qiao, Rong-Hua Li, Qi Zhang, Guoren Wang},
    journal={arXiv preprint arXiv:2403.05775},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.05775},
    primaryClass={cs.DS}
}