Local Search for Diversified Top-k s-plex Search Problem (Student Abstract)

Authors

  • Jun Wu Northeast Normal University
  • Minghao Yin Northeast Normal University

DOI:

https://doi.org/10.1609/aaai.v35i18.17961

Keywords:

Top-$k$ $s$-plex Search, Local Search, Mixed Integer Linear Program

Abstract

The diversified top-k s-plex (DTKSP) search problem aims to find k maximal s-plexes that cover the maximum number of vertices with lower overlapping in a given graph. In this paper, we first formalize the diversified top-k s-plex search problem and prove the NP-hardness of it. Second, we proposed a local search algorithm for solving the diversified top-k s-plex search problem based on some novel ideas. Experiments on real-world massive graphs show the effectiveness of our algorithm.
AAAI-21 Proceedings Cover

Downloads

Published

2021-05-18

How to Cite

Wu, J., & Yin, M. (2021). Local Search for Diversified Top-k s-plex Search Problem (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 35(18), 15929–15930. https://doi.org/10.1609/aaai.v35i18.17961

Issue

Vol. 35 No. 18: AAAI-21 Student Papers and Demonstrations

Section

AAAI Student Abstract and Poster Program