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

Mingyu Xiao, Weibo Lin, Yuanshun Dai, Yifeng Zeng

    Research output: Contribution to conferencePaperpeer-review

    54 Downloads (Pure)


    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 languageEnglish
    Publication statusPublished - 4 Feb 2017
    Event31st AAAI Conference on Artificial Intelligence - San Francisco, United States
    Duration: 4 Feb 20179 Feb 2017


    Conference31st AAAI Conference on Artificial Intelligence
    Abbreviated titleAAAI-17
    Country/TerritoryUnited States
    CitySan Francisco


    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