Computing Unbalanced Degree of Signed Networks Based on Culture Algorithm

Signed network is the network with both positive and negative links. Many real-world complex systems can be represented as signed networks, which are unbalanced according to structural balance theory. Unbalanced degree of signed networks is the distance to exact balance. Evaluating unbalanced degree of signed networks is a NP-hard problem, which has attracted many attentions. Many approaches are developed to compute structural balance. However, the results obtained by these approaches are unsatisfactory. In this study, the computation of unbalanced degree is convert to an optimization problem whose object function is come from the Hamiltonian of Edwards-Anderson spin glass model. We use a new Cultural Algorithm named CA-SNB to solve the optimization problem. The Cultural Algorithm, a new computable framework of Evolution Algorithm, has been successfully applied to many areas. In CA-SNB, the evolution of population space and belief space is based on Genetic Algorithm and greedy strategy respectively. Experiments on social and biological networks show the excellent effectiveness and efficiency of the proposed method.