A memetic algorithm for computing and transforming structural balance in signed networks

• This paper aims at reducing the potential conflicts in real-world signed networks.
• We model the computation of structural balance as the optimization of energy index.
• We present a more general energy function Hw incorporated with transformation cost.
• We model the transformation of structural balance as the optimization of Hw.
• We propose a fast memetic algorithm to solve the modeled optimization problems.

Structural balance enables a comprehensive understanding of the potential tensions and conflicts of signed networks, and its computation and transformation have attracted increasing attention in recent years. The balance computation aims at evaluating the distance from an unbalanced network to a balanced one, and the balance transformation is to convert an unbalanced network into a balanced one. In this paper, firstly, we model the balance computation of signed networks as the optimization of an energy function. Secondly, we model the balance transformation as the optimization of a more general energy function incorporated with transformation cost. Finally, a multilevel learning based memetic algorithm, which incorporates network-specific knowledge such as the neighborhoods of node, cluster and partition, is proposed to solve the modeled optimization problems. Systematical experiments in real-world social networks demonstrate the superior performance of the proposed algorithm compared with the state-of-the-art algorithms on the computation and transformation of structural balance. The results also show that our method can resolve the potential conflicts of signed networks with the minimum cost.