Approaches for finding cohesive subgroups in large-scale social networks via maximum k-plex detection

Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


A k-plex is a clique relaxation introduced in social network analysis to model cohesive social subgroups that allows for a limited number of nonadjacent vertices (strangers) inside the cohesive subgroup. Several exact algorithms and heuristic approaches to find a maximum-size k-plex in the graph have been developed recently for this NP-hard problem. This article develops a greedy randomized adaptive search procedure (GRASP) for the maximum k-plex problem. We offer a key improvement in the design of the construction procedure that alleviates a drawback observed in multiple past studies. In existing construction heuristics, k-plexes found for smaller values of parameter k are sometimes not found for larger k even though they are feasible; instead inferior solutions are found. We identify the reasons behind this behavior and address these in our new construction procedure. We then show that an existing exact algorithm for solving this problem on power-law graphs can be considerably enhanced by using GRASP. The overall approach is able to solve the problem to optimality on massive social networks, including some with several million vertices and edges. These are orders of magnitude larger than the largest real-life social networks on which this problem has been solved to optimality in the current literature.

Original languageEnglish
Pages (from-to)388-407
Number of pages20
Issue number4
StatePublished - 1 Jul 2017
Externally publishedYes


  • cohesive subgroups
  • greedy randomized adaptive search procedure
  • k-plex
  • metaheuristic
  • social network analysis


Dive into the research topics of 'Approaches for finding cohesive subgroups in large-scale social networks via maximum k-plex detection'. Together they form a unique fingerprint.

Cite this