A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis

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.