Study On Structural Balance For Signed Network Based On Decomposition-based Multi-objective Optimization

In the 21 st century, with the rapid development of science and technology, the field of information is ever-changing, and a variety of network applications emerge in an endless stream. Rapid development of the various shopping sites, social networking sites and online communities is subtly changing our lifestyles, ways of thinking. Under such background, signed network becomes more and more important in the research on comprehension and prediction of the topology, function, dynamic development of complex network. For example, for personalized recommendation and user attitudes forecasting, the accuracy of recommendation and forecasting will be improved when the effect of negative information is taken into consideration. Structural balance in signed network has attracted much attention from many scholars,and a lot of meaningful research results have been achieved. But most of the researches were conducted in the heuristic method or a single-objective optimization method. In these methods, only one solution can be returned in a single run, so there would be a lot of limitations in the application. Thesis handles the structural balance problem by proposing a multi-objective optimization model and a cluster-based local search strategy from the perspective of multi-objective optimization along with the concrete factors influencing the network balance. The main work is as follows.First, by reading a lot of papers on the structural balance of signed network, we have understood the significance of signed network and the existing algorithms for structural balance in a macro sense.Second, based on the weak balance theory, we model the structural balance of signed network as a multi-objective optimization problem according to the two kinds of imbalanced factors from the perspective of multi-objective optimization. The model contains two objective functions, negin and posout, namely the total number of within-cluster negative edges and the total number of between-cluster positive edges, respectively. Due to the relatively low computational complexity and even distribution of PF, MOEA/D is adopted as the framework of our algorithm. Meanwhile, based on the specific network structural balance problem, we design a multi-objective optimization algorithm, termed as MOEA / D-SNB, by incorporating the one-way crossover and positive-neighborhood-based mutation which can make full use of network topology to solve the proposed multi-objective optimization problem. The comparison experiments onsynthetic and real network data sets with MODPSO and FEC show the validity of our method on handling the structural balance problem.Third, in order to further improve the performance of MOEA/D-SNB, a cluster-based local search strategy which takes the structural balance into consideration is designed. The proposed local search focuses on the optimization of posout. The neighborhood of network partition is defined from the perspective of cluster. The network partition updates itself to the best neighbor which can makes the largest decrease in posout in each neighborhood. The final network partition has no such cluster pairs that only positively linked. Meanwhile, in order to avoid the loss of elites, the external population EP is backuped before the local search process. In the end, the old and new external population are merged and nondominated sorted. And the set of nondominated solutions is returned as the result. Through the experiments on network datasets by MOEA/D-SNB and MOEA/D-SNB-Ls, we can say that the proposed local search operator can effectively reduce the imbalanced degree of the network partition with high posout value.