Structural Balance Analysis In Signed Networks Based On Evolutionary Algorithm

Many real-world complex systems can be represented as networks, such as social network, biological network, collaboration network, the World-Wide-Web, and power grid, etc. Networks are usually represented by graphs, where nodes(or vertices)represent the objects and edges represent the interactions among these objects. In most cases, the edges typically indicate friendship, collaboration, sharing information, and all such things which have positive connotations. Social networks reflect a largely similar view that the connections mean friends, fans, followers, and so on. But in most networks, there are also negative effects at work. Some relations are friendly, but others are hostile; interactions between people or groups are regularly beset by controversy,disagreement, and sometimes outright conflict. Networks which have the characteristic mentioned above are called as signed networks.In the dynamical evolution of networks, the signed networks implicitly seek out structural balance. Structural balance is a large area of study in signed networks, and it is intrinsically a global property of the whole network. In many cases, in order to understand the structure of signed networks, we need to measure the unbalanced degree(i.e., measure a distance to exact balance). Computation of global structural balance offers an approach to solve this problem. More generally, computing global structural balance corresponds to computing the ground-state of a(nonplanar) Ising spin glass,which is a well-known nondeterministic polynomial-time hard(NP-hard) problem. In this paper, in order to fast compute the global structural balance of the signed networks,we propose a novel approach which tries to optimize the energy function by employing Evolutionary Algorithm. Our major contributions are outlined as follows:1. An analytic method used for fast computing global structural balance in signed networks is proposed. This method is based on genetic algorithm, called GA-SB. This part first introduces the evolutionary algorithm and genetic algorithm in short. Then, we describe the conception of energy function in detail. Afterwards we introduce the design of GA-SB in detail combining the specific situation of structural balance, and test GA-SB on social and biological networks. At last, we propose the lack of GA-SB by analyzing the experimental results. According to the experimental results, we can find that the GA-SB is effective only in small-scale networks. Its performance is poorer when the signed network is large-scale. The reason why GA-SB can’t have better performances is that the algorithm’s convergence speed is very slow. Meanwhile, the search process of GA-SB trap in local optimum easily.2. Because the GA-SB don’t have better performances, we improve it and propose another analytic method used for fast computing global structural balance in signed networks. This method is based on memetic algorithm, called Meme-SB. The proposed algorithm combines genetic algorithm and a greedy strategy as the local search procedure. This part first introduces the memetic algorithm. From the view of optimization, memetic algorithm has been proved to be more efficient and more effective than traditional genetic algorithm for a few problem domains, especially for NP-hard problems. Then, we introduce the design of Meme-SB in detail combining the specific situation of structural balance. we describe the local search procedure in detail and give the algorithm framework at the same time. At last, we use social networks and biological networks to test if Meme-SB can effectively compute global structural balance. The experimental results show that Meme-SB has better performances than the two compared algorithms. The comparative results on both social and biological networks demonstrate the effectiveness and efficiency of Meme-SB on computing global structural balance. In addition, according to the minimum value of the energy function, we can get a connotative information that how many edges(or pairwise relationships) which lead to the unbalance of the network exist. By changing the signs of these edges into the opposite, we can obtain an exactly balanced network.