Cluster detection in large-scale social networks using κ-plexes

Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to conferencePaperpeer-review

1 Scopus citations


Cliques have long been the standardmodel for cluster detection in graph-based datamining. However, clique definition is overly restrictive making the approach unsuitable for real-life networks that are constructed based on erroneous or incomplete data. A parameterized clique relaxation called a κ-plex that overcomes this drawback was introduced in social network analysis for detecting cohesive social subgroups. Several exact algorithms for the maximum κ-plex problem were recently developed. However, heuristic approaches which are more suitable for the analysis of largescale social networks are unavailable. This article develops an effective greedy randomized adaptive search procedure (GRASP) and compares its performance on standard benchmarks against integer programming heuristics available in a well-known commercial solver. More significantly, this article demonstrates that an exact algorithm for solving this problem on power-law graphs can be considerably enhanced by using GRASP, so that the combination is able to solve the problem to optimality on much larger social networks than previously known.

Original languageEnglish
Number of pages10
StatePublished - 1 Jan 2012
Externally publishedYes
Event62nd IIE Annual Conference and Expo 2012 - Orlando, FL, United States
Duration: 19 May 201223 May 2012


Conference62nd IIE Annual Conference and Expo 2012
Country/TerritoryUnited States
CityOrlando, FL


  • Cluster detection
  • Cohesive subgroups
  • Graph-based data mining
  • Maximum κ-plex problem
  • Social network analysis


Dive into the research topics of 'Cluster detection in large-scale social networks using κ-plexes'. Together they form a unique fingerprint.

Cite this