A hybrid optimization algorithm for structural balance model based on influence between nodes and community quality

• A novel multi-objective model for structural balance problem is proposed. • Community quality and influence between nodes are considered in the novel model. • The proposed EDLS operator is integrated into NSGA-II to optimize the novel model. • A novel evaluation method instead of computing real objective function is proposed. The aim of structural balance problem is to balance an unbalanced signed social network with the minimum cost of changing edges in the network. However, the existing structural balance models usually neglect the influence between nodes, and simultaneously, fail to achieve a desirable trade-off between the structural balance cost and the community quality, which does not fit the nature of the practical network scenarios and then affects the performance of balancing the complex network structure. For this issue, this paper first proposes an improved structural balance model, which jointly takes the influence between nodes and the community quality into account. Then, in order to solve the above model, this paper designs an enhanced multi-objective optimizer based on the non-dominated sorting genetic algorithm framework, which utilizes the estimation of distribution model and a local search strategy to improve the search ability in the discrete search space. Especially, the proposed optimizer has a better ability of exploring the complex solution space and exploiting the local optimal region with a fast convergence rate. However, the use of the estimation of distribution operation and the local search operation may lead to expensive computational cost. Then, to alleviate the computational complexity, this paper introduces a novel evaluation method, which only calculates the total weights of positive edges and negative edges that need to be changed to balance the network, instead of computing the real objective function in the local search operation. Experiments on the different networks confirm the effectiveness and efficiency of the proposed algorithm.