A clique model is one of the most important techniqueson the cohesive subgraph detection; however, its applicationsare rather limited due to restrictive conditionsof the model. Hence much research resorts to k-plex - agraph in which any vertex is adjacent to all but at mostk vertices - which is a relaxation model of the clique. Inthis paper, we study the maximum k-plex problem andpropose a fast algorithm to compute maximum k-plexesby exploiting structural properties of the problem. In ann-vertex graph, the algorithm computes optimal solutionsin cnnO(1) time for a constant c < 2 depending only on k. To the best of our knowledge, this is thefirst algorithm that breaks the trivial theoretical boundof 2n for each k 3. We also provide experimental resultsover multiple real-world social network instancesin support.
|Publication status||Published - 4 Feb 2017|
|Event||31st AAAI Conference on Artificial Intelligence - San Francisco, United States|
Duration: 4 Feb 2017 → 9 Feb 2017
|Conference||31st AAAI Conference on Artificial Intelligence|
|Period||4/02/17 → 9/02/17|