  In this study, we address the complex issue of graph clustering in signed
graphs, which are characterized by positive and negative weighted edges
representing attraction and repulsion among nodes, respectively. The primary
objective is to efficiently partition the graph into clusters, ensuring that
nodes within a cluster are closely linked by positive edges while minimizing
negative edge connections between them. To tackle this challenge, we first
develop a scalable multilevel algorithm based on label propagation and FM local
search. Then we develop a memetic algorithm that incorporates a multilevel
strategy. This approach meticulously combines elements of evolutionary
algorithms with local refinement techniques, aiming to explore the search space
more effectively than repeated executions. Our experimental analysis reveals
that this our new algorithms significantly outperforms existing
state-of-the-art algorithms. For example, our memetic algorithm can reach
solution quality of the previous state-of-the-art algorithm up to four orders
of magnitude faster.
