Proceedings

A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem

Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, Zhang-Hua Fu

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 1689-1696.

https://doi.org/10.24963/ijcai.2021/233

Keywords

  • Data Mining: Mining Graphs, Semi Structured Data, Complex Data
  • Heuristic Search and Game Playing: Combinatorial Search and Optimisation
  • Heuristic Search and Game Playing: Heuristic Search

Abstract

Given an undirected graph, the Maximum k-plex Problem (MKP) is to find a largest induced subgraph in which each vertex has at most k−1 non-adjacent vertices. The problem arises in social network analysis and has found applications in many important areas employing graph-based data mining. Existing exact algorithms usually implement a branch-and-bound approach that requires a tight upper bound to reduce the search space. In this paper, we propose a new upper bound for MKP, which is a partitioning of the candidate vertex set with respect to the constructing solution. We implement a new branch-and-bound algorithm that employs the upper bound to reduce the number of branches. Experimental results show that the upper bound is very effective in reducing the search space. The new algorithm outperforms the state-of-the-art algorithms significantly on real-world massive graphs, DIMACS graphs and random graphs.

Hua Jiang, Dongming Zhu, Zhichao Xie, Shaowen Yao, and Zhang-hua Fu. 2021. A New Upper Bound Based on Vertex Partitioning for the Maximum K-plex Problem. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 1689–1696. https://doi.org/10.24963/ijcai.2021/233
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards