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

Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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
JournalNetworks
Volume69
Issue number4
DOIs
Publication statusPublished - 1 Jul 2017
Externally publishedYes

    Fingerprint

Keywords

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

Cite this