An Exact Algorithm for Maximum K-Plexes in Massive Graphs
Abstract
The maximum k-plex, a generalization of maximum clique, is used to cope with a great number of real-world problems. The aim of this paper is to propose a novel exact k-plex algorithm that can deal with large-scaled graphs with millions of vertices and edges. Specifically, we first propose several new graph reduction methods through a careful analyzing of structures of induced subgraphs. Afterwards, we present a preprocessing method to simplify initial graphs. Additionally, we present a branch-and-bound algorithm integrating the reduction methods as well as a new dynamic vertex selection mechanism. We perform intensive experiments to evaluate our algorithm, and show that the proposed strategies are effective and our algorithm outperforms state-of-the-art algorithms, especially for real-world massive graphs.
Cite
Text
Gao et al. "An Exact Algorithm for Maximum K-Plexes in Massive Graphs." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/201Markdown
[Gao et al. "An Exact Algorithm for Maximum K-Plexes in Massive Graphs." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/gao2018ijcai-exact/) doi:10.24963/IJCAI.2018/201BibTeX
@inproceedings{gao2018ijcai-exact,
title = {{An Exact Algorithm for Maximum K-Plexes in Massive Graphs}},
author = {Gao, Jian and Chen, Jiejiang and Yin, Minghao and Chen, Rong and Wang, Yiyuan},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1449-1455},
doi = {10.24963/IJCAI.2018/201},
url = {https://mlanthology.org/ijcai/2018/gao2018ijcai-exact/}
}