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

Mingyu Xiao, Weibo Lin, Yuanshun Dai, Yifeng Zeng

    Research output: Contribution to conferencePaper

    22 Downloads (Pure)

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

    Conference

    Conference31st AAAI Conference on Artificial Intelligence
    Abbreviated titleAAAI-17
    CountryUnited States
    CitySan Francisco
    Period4/02/179/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.