A Research Of Structural Balance Of Signed Network Based On Evolutionary Algorithm

Structural balance is regarded as a fundamental social theory, it's the basic theory to discuss other properties of network. It was proposed by Heider based on social psychology theory in the 1940 s. The relations between people are parted into two types, positive and negative. It is used to analyze the dynamic development of the relationship. Later, it was generalized by Cartwright and Harary, from the perspective of triangular relations. The research of structural balance now has attracted many scholars. Now, they have made breakthrough. They make us have a clearer outlook for the significance and practical value of network structural balance studies. But there are still some limitations about the traditional study of the structural balance. Such as, algorithms and models, most of the models are the single objectives, each run of these algorithms can only generate one solution. But, a signed network often has many structures for its dynamic development. In this thesis, we proposed a new model and algorithm to solve these problems. It works as follows:(1) For the limitations of traditional methods, we propose a new approach, the PSOADM, to solve some problems of the structural balance. This method has two major steps. And it has three innovations. First, this thesis presents a multi-objective model; Very often, such a problem is NP hard, it involves evolutionary algorithm(MODPSO-II) to solve structural balance problem firstly; and third, a problem-specific model selection strategy is devised to select the best Pareto solution from the Pareto front produced by the first step. The best Pareto solution is then decoded into the corresponding network community structure. Afterward, imbalanced edges are flipped so as to make the network structurally balanced.(2) The traditional models have an expensive computational or space complexity, and can obtain one structure only. It seriously violates the dynamic development of the network. Often the network is divided into two parts which is a serious polarization problem. The first step of PSOADM is a multi-objective model and provides us with a variety of structures. The model of the first step of PSOADM is the definition of the community detection which is not accordance with the theoretical of structural balance. Based on the basic theory of the structure balance, we also consider the negative edges within clusters and the positive edges between clusters. If there are only positive edges within clusters and negative edges between clusters, the network is balanced. So, it is reasonable for taking into account the relationships between clusters and within the clusters. Based on the studied models and the structural balance theory, a new multi-objective model is suggested, and it is optimized by an improved multi-objective discrete particle swarm optimization algorithm. Each single run of the algorithm can yield a set of Pareto solutions. Each of Pareto solutions represents a certain network partition that divides a signed network into many clusters. It can provide many choices for decider.