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 Citations (Scopus)

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
StatePublished - 1 Jul 2017
Externally publishedYes

Fingerprint

Electric network analysis
Computational complexity

Keywords

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

Cite this

@article{868705b202f04b35a2b516565254167e,
title = "Approaches for finding cohesive subgroups in large-scale social networks via maximum k-plex detection",
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.",
keywords = "cohesive subgroups, greedy randomized adaptive search procedure, k-plex, metaheuristic, social network analysis",
author = "Zhuqi Miao and Balabhaskar Balasundaram",
year = "2017",
month = "7",
day = "1",
doi = "10.1002/net.21745",
language = "English",
volume = "69",
pages = "388--407",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
number = "4",

}

Approaches for finding cohesive subgroups in large-scale social networks via maximum k-plex detection. / Miao, Zhuqi; Balasundaram, Balabhaskar.

In: Networks, Vol. 69, No. 4, 01.07.2017, p. 388-407.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Miao, Zhuqi

AU - Balasundaram, Balabhaskar

PY - 2017/7/1

Y1 - 2017/7/1

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

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

KW - cohesive subgroups

KW - greedy randomized adaptive search procedure

KW - k-plex

KW - metaheuristic

KW - social network analysis

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

U2 - 10.1002/net.21745

DO - 10.1002/net.21745

M3 - Article

AN - SCOPUS:85018883049

VL - 69

SP - 388

EP - 407

JO - Networks

JF - Networks

SN - 0028-3045

IS - 4

ER -