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

Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to conferencePaper

1 Scopus citations

Abstract

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
Pages2871-2880
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

Conference

Conference62nd IIE Annual Conference and Expo 2012
CountryUnited States
CityOrlando, FL
Period19/05/1223/05/12

Keywords

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

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

  • Cite this

    Miao, Z., & Balasundaram, B. (2012). Cluster detection in large-scale social networks using κ-plexes. 2871-2880. Paper presented at 62nd IIE Annual Conference and Expo 2012, Orlando, FL, United States.