A Distributed Multilevel Memetic Algorithm for Signed Graph Clustering

In real-world applications, interactions between two entities can be usually represented by signed graphs, i.e., graphs containing edges with positive weight representing node attraction and edges with negative weight representing node repulsion. A relevant problem for the analysis of a graph is to find a graph clustering, i.e., a partition of its nodes into clusters such that nodes contained in the same cluster are densely connected by positive edges and sparsely connected by negative edges. In this work, we propose and engineer all the details of a memetic algorithm based on a novel multilevel approach for the problem. Experimental results show that our memetic strategy computes significantly better solutions than the current state-of-the-art.