Research On The Structural Balance And Robustness Problem In Signed Networks

Many systems can be modeled as complex networks in the real life.The nodes in the network represent the individuals in the system,and the edges in the network represent the relationship between individuals.In recent years,great progress has been made in the research of complex networks,but there are still gaps for some special networks.The signed network,as a kind of special networks in which edges are endowed with positive or negative attributes,is usually used to describe the conflict relationships between individuals in the network.Hence,the research in the signed network is significant for both scientific interest and applicable value.Taking the signed network as the research target,this paper studies the problems of structural balance and robustness.The main purposes and research contents are as follows.As one of the most basic problems in signed networks,the issue of structural balance has attracted extensive attention.This problem aims to find a partition of a signed network to maximize the number of positive edges in the partition subset and that of negative edges between subsets.Many researches attempt to solve this problem by the accurate algorithms based on mathematical programming.These algorithms are able to calculate the frustration index of small and medium-sized signed networks but become difficult to obtain the solution in an acceptable time when applied to the large-scale signed networks.Meanwhile,intelligent optimization algorithms are proposed to solve the problem in large signed networks but there are still some drawbacks such as too many parameters and low efficiency.In view of the above situations,an efficient iterative greedy algorithm is designed in this paper to quickly solve the structural balance problem.The algorithm takes a two-stage local search strategy as the main search method,uses a constructive heuristic process to generate the initial solution,increases the diversity of solutions with the help of destruction and reconstruction operators,and finally gives some acceleration measures to improve the efficiency of the algorithm.The experimental results show that,compared with the existing intelligent optimization algorithms,the proposed iterative greedy algorithm has obvious advantages in efficiency for small and medium-sized networks.For large-scale signed networks,the algorithm is superior to other intelligent optimization algorithms in terms of both computation time and solution quality.On the basis of quickly solving the structural balance problem,this paper further studies the problem of robustness in signed networks.The problem of network robustness has been deeply studied in general complex networks,but there are some difficulties when extending it to signed networks.For example,the classical robustness metrics are not suitable for signed networks and the degree-based attack models ignore the attributes of edges.Therefore,there is few researches on the robustness of signed networks.In this paper,the frustration index,obtained when solving the structural balance problem,is considered and then a measurement to the signed network robustness is proposed.Four malicious attack models are established based on different centrality measurement of nodes and the process of malicious attack in signed networks is given.Afterwards,taking the node protection strategy as an example,this paper designs two greedy algorithms based on centrality metric and the frustration index,which aim at selecting some nodes for protection to improve the robustness of signed networks.Finally,the paper summarizes the characteristics of different attack models in signed networks through experiments on real-world network data sets,and verifies the effectiveness of the two greedy algorithms designed in this paper in improving network robustness.