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

Zhuqi Miao, Balabhaskar Balasundaram

Research output: Contribution to conferencePaper

1 Citation (Scopus)

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

Fingerprint

Integer programming
Electric network analysis

Keywords

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

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.
Miao, Zhuqi ; Balasundaram, Balabhaskar. / Cluster detection in large-scale social networks using κ-plexes. Paper presented at 62nd IIE Annual Conference and Expo 2012, Orlando, FL, United States.10 p.
@conference{2b962e20000e474cb89769f879db2c60,
title = "Cluster detection in large-scale social networks using κ-plexes",
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.",
keywords = "Cluster detection, Cohesive subgroups, Graph-based data mining, Maximum κ-plex problem, Social network analysis",
author = "Zhuqi Miao and Balabhaskar Balasundaram",
year = "2012",
month = "1",
day = "1",
language = "English",
pages = "2871--2880",
note = "null ; Conference date: 19-05-2012 Through 23-05-2012",

}

Miao, Z & Balasundaram, B 2012, 'Cluster detection in large-scale social networks using κ-plexes' Paper presented at 62nd IIE Annual Conference and Expo 2012, Orlando, FL, United States, 19/05/12 - 23/05/12, pp. 2871-2880.

Cluster detection in large-scale social networks using κ-plexes. / Miao, Zhuqi; Balasundaram, Balabhaskar.

2012. 2871-2880 Paper presented at 62nd IIE Annual Conference and Expo 2012, Orlando, FL, United States.

Research output: Contribution to conferencePaper

TY - CONF

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

AU - Miao, Zhuqi

AU - Balasundaram, Balabhaskar

PY - 2012/1/1

Y1 - 2012/1/1

N2 - 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.

AB - 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.

KW - Cluster detection

KW - Cohesive subgroups

KW - Graph-based data mining

KW - Maximum κ-plex problem

KW - Social network analysis

UR - http://www.scopus.com/inward/record.url?scp=84900328119&partnerID=8YFLogxK

M3 - Paper

AN - SCOPUS:84900328119

SP - 2871

EP - 2880

ER -

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