Premium
Approaches for finding cohesive subgroups in large‐scale social networks via maximum k ‐plex detection
Author(s) -
Miao Zhuqi,
Balasundaram Balabhaskar
Publication year - 2017
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.21745
Subject(s) - heuristics , grasp , clique , heuristic , computer science , relaxation (psychology) , greedy algorithm , key (lock) , mathematical optimization , social network analysis , combinatorics , social network (sociolinguistics) , mathematics , discrete mathematics , psychology , social psychology , computer security , world wide web , social media , programming language
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. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 388–407 2017