Research On Complex Network Reconstruction Algorithm

The complex systems is very common in real life applications.In order to facilitate science research,we usually abstract complex systems into complex networks.The individuals in complex systems correspond to nodes in complex networks,and the relationships among individuals in complex systems correspond to the edges of nodes in complex networks.The study of complex networks has very important practical significance.The topology of a network is crucial to its functions and collective behaviors.In many cases,various data are obtained from the network,for example,information spreading data,gene expression microarray data,game data,but the topology of the network is unknown.Reconstructing the topology of the network from those observed data is meaningful in many practical applications.The work of this paper is to study the complex network reconstruction algorithm.The game matrix equation is constructed based on the game data,the solution space and its properties are defined,and the heuristic local search method is proposed.A hybrid algorithm for network reconstruction and a fast algorithm for network reconstruction are proposed.Specific work as follows: 1.The paper studies the characteristics of game data.Because it can be easily extended to various types of networks in various fields,it is usually used as a benchmark data.The game matrix equation is constructed according to the game strategy and the payoff matrix and solution space of the matrix equation is defined.The properties of the solution space in different data quantities are studied.Based on the study of the properties of solution space,a heuristic local search method based on game data under two or more rounds of game data are proposed.And the paper gives the proof of the theories.2.This paper designs a hybrid algorithm for network reconstruction,based on the observed game data to reconstruct the network.The proposed hybrid algorithm decomposes the network reconstruction problem into the problem of reconstructing each node in the network in turn simplifies complex problems.And we do not need to consider the network is sparse or close,and do not need to consider whether the amount of data is sufficient.The edges of each node are described by the column vectors of the corresponding network adjacency matrix.The initial population,such as the initial possible solution vector,can be obtained by the proposed genetic algorithm.Furthermore,the true solution vector can be obtained by the proposed heuristic local search method.Experiments show that the proposed hybrid algorithm is more accurate than the compressive sensing algorithm.3.This paper proposed a fast algorithm for network reconstruction,which uses the method of solving game matrix equations directly to reconstruct the network.According to the theory of matrix equation and Moore-Penrose inverse matrices,the method of solving matrix equation and the properties of its solution are studied.In the infinite number of solutions of the matrix equation,we choose the minimal norm least squares solution with uniqueness to study its relation with the actual situation of the network,and deduce the topology of the network.The influence of different solutions Moore-Penrose inverse matrices on network reconstruction is analyzed through experiments.A fast method for solving Moore-Penrose inverse matrices is applied to the algorithm.The relationship between the average degree of network and the network parameters set during reconstruction is verified by experiments.Experiments show that in the case of relatively abundant data,we can quickly and accurately realize the complete reconstruction of the network.