Scaling Up k-Clique Densest Subgraph Detection
Proceedings of the ACM on Management of Data · 26.05.2023 · 1 (1) · 1-26
DOI: 10.1145/3588923 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 30.05.2023. Verfasst von Yizhang He und 4 weiteren Autor:innen. Die Arbeit wurde bisher 24-mal zitiert (Crossref) und nennt 60 Literaturangaben. Gefördert von: National Natural Science Foundation of China, Australian Research Council.
Abstract (Originalsprache)
In this paper, we study the k-clique densest subgraph problem, which detects the subgraph that maximizes the ratio between the number of k-cliques and the number of vertices in it. The problem has been extensively studied in the literature and has many applications in a wide range of fields such as biology and finance. Existing solutions rely heavily on repeatedly computing all the k-cliques, which are not scalable to handle large k values on large-scale graphs. In this paper, by adapting the idea of "pivoting", we propose the SCT*-Index to compactly organize the k-cliques. Based on the SCT*-Index, our SCTL algorithm can directly obtain the k-cliques from the index and efficiently achieve near-optimal approximation. To further improve SCTL, we propose SCTL* that includes novel graph reductions and batch-processing optimizations to reduce the search space and decrease the number of visited k-cliques, respectively. As evaluated in our experiments, SCTL* significantly outperform existing approaches by up to two orders of magnitude. In addition, we propose a sampling-based approximate algorithm that can provide reasonable approximations for any k value on billion-scale graphs. Extensive experiments on 12 real-world graphs validate both the efficiency and effectiveness of the proposed techniques.
Förderung
- National Natural Science Foundation of China
- Australian Research Council
Zitieren
APA
He, Y., Wang, K., Zhang, W., Lin, X., & Zhang, Y. (2023). Scaling Up k-Clique Densest Subgraph Detection. Proceedings of the ACM on Management of Data, 1(1), 1-26. https://doi.org/10.1145/3588923
Vancouver
He Y, Wang K, Zhang W, Lin X, Zhang Y. Scaling Up k-Clique Densest Subgraph Detection. Proceedings of the ACM on Management of Data. 2023;1(1):1-26. doi:10.1145/3588923
BibTeX
@article{He2023,
author = {He, Yizhang and Wang, Kai and Zhang, Wenjie and Lin, Xuemin and Zhang, Ying},
title = {Scaling Up k-Clique Densest Subgraph Detection},
journal = {Proceedings of the ACM on Management of Data},
year = {2023},
volume = {1},
number = {1},
pages = {1--26},
doi = {10.1145/3588923}
}
EUVIMED