Fast computing global structural balance in signed networks based on memetic algorithm

作者：Sun, Yixiang; Du, Haifeng; Gong, Maoguo^*; Ma, Lijia; Wang, Shanfeng

来源：Physica A: Statistical Mechanics and Its Applications , 2014, 415: 261-272.

DOI：10.1016/j.physa.2014.07.071

• Signed network
• Structural balance
• Global property
• Memetic algorithm
• Genetic algorithm
• Local search

Structural balance is a large area of study in signed networks, and it is intrinsically a global property of the whole network. Computing global structural balance in signed networks, which has attracted some attention in recent years, is to measure how unbalanced a signed network is and it is a nondeterministic polynomial-time hard problem. Many approaches are developed to compute global balance. However, the results obtained by them are partial and unsatisfactory. In this study, the computation of global structural balance is solved as an optimization problem by using the Memetic Algorithm. The optimization algorithm, named Meme-SB, is proposed to optimize an evaluation function, energy function, which is used to compute a distance to exact balance. Our proposed algorithm combines Genetic Algorithm and a greedy strategy as the local search procedure. Experiments on social and biological networks show the excellent effectiveness and efficiency of the proposed method.

• 出版日期2014-12-1
• 单位西安电子科技大学; 西安交通大学