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

Authors

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

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.

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/17961

Issue

Section

AAAI Student Abstract and Poster Program