Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding

Authors

  • Yi Zhou University of Electronic Science and Technology of China
  • Shan Hu University of Electronic Science and Technology of China
  • Mingyu Xiao University of Electronic Science and Technology of China
  • Zhang-Hua Fu Shenzhen Institute of Artificial Intelligence and Robotics for Society; The Chinese University of Hong Kong, Shenzhen

DOI:

https://doi.org/10.1609/aaai.v35i14.17477

Keywords:

Heuristic Search, Applications, Graph Mining, Social Network Analysis & Community

Abstract

In a graph, a k-plex is a vertex set in which every vertex is not adjacent to at most k vertices of this set. The maximum k-plex problem, which asks for the largest k-plex from the given graph, is a key primitive in a variety of real-world applications like community detection and so on. In the paper, we develop an exact algorithm, Maplex, for solving this problem in real world graphs practically. Based on the existing first-order and the novel second-order reduction rules, we design a powerful preprocessing method which efficiently removes redundant vertices and edges for Maplex. Also, the graph color heuristic is widely used for overestimating the maximum clique of a graph. For the first time, we generalize this technique for bounding the size of maximum k-plex in Maplex. Experiments are carried out to compare our algorithm with other state-of-the-art solvers on a wide range of publicly available graphs. Maplex outperforms all other algorithms on large real world graphs and is competitive with existing solvers on artificial dense graphs. Finally, we shed light on the effectiveness of each key component of Maplex.

Downloads

Published

2021-05-18

How to Cite

Zhou, Y., Hu, S., Xiao, M., & Fu, Z.-H. (2021). Improving Maximum k-plex Solver via Second-Order Reduction and Graph Color Bounding. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12453-12460. https://doi.org/10.1609/aaai.v35i14.17477

Issue

Section

AAAI Technical Track on Search and Optimization