  We propose a hybrid heuristic algorithm for solving the Heaviest k-Subgraph
Problem in online social networks -- a combinatorial graph optimization problem
central to many important applications in weighted social networks, including
detection of coordinated behavior, maximizing diversity of a group of users,
and detecting social groups. Our approach builds upon an existing metaheuristic
framework known as Variable Neighborhood Search and takes advantage of
empirical insights about social network structures to derive an improved
optimization heuristic. We conduct benchmarks in both real life social networks
as well as synthetic networks and demonstrate that the proposed modifications
match and in the majority of cases supersede those of the current
state-of-the-art approaches.
