Partitioning signed networks using relocation heuristics, tabu search, and variable neighborhood search

Recently, there have been significant advancements in the development of exact methods and metaheuristics for partitioning signed networks. The metaheuristic advancements have led commonly to adverse implications for multiple restart (multistart) relocation heuristics for these networks. Most notably, it has been reported that multistart relocation heuristics are not computationally feasible for large signed networks with thousands or tens of thousands of vertices. In this paper, we show that combining multistart relocation heuristics with tabu search or variable neighborhood search can rapidly produce partitions of the vertices of signed networks that are competitive with those obtained using existing metaheuristics.