### Abstract

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.

Original language | English |
---|---|

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

Conference | 31st AAAI Conference on Artificial Intelligence |
---|---|

Abbreviated title | AAAI-17 |

Country | United States |

City | San Francisco |

Period | 4/02/17 → 9/02/17 |

## Fingerprint Dive into the research topics of 'A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis'. Together they form a unique fingerprint.

## Cite this

Xiao, M., Lin, W., Dai, Y., & Zeng, Y. (2017).

*A Fast Algorithm to Compute Maximum k-Plexes in Social Network Analysis*. Paper presented at 31st AAAI Conference on Artificial Intelligence, San Francisco, United States.