Research On Complex Network Dynamics And Reconstruction

Complex network is the abstract of complex system. Different kinds of diverse and complex networks exist in both nature and the human society, such as biological networks, neural networks, personnel networks, computer networks and so on. However, individuals in complex system correspond to nodes in complex network; while relationships between the individuals in the system correspond to edges between the nodes in the network. The further study of these networks not only has an essential and practical significance to people’s work and life, but also has a profoundly scientific significance for the development of nature and the whole human society.The ultimate goal of the research on complex networks can be concluded as follows. On one hand, understand how the topology structure of the network affects different kinds of dynamic processes. On the other hand, understand how the dynamical evolutionary process determines the topology structure of the network. In this paper, we deeply study the coupled process of synchronization in the network first. Based on the understanding of principles of synchronous implementation, a phase clustering model is introduced, which is easy to achieve the synchronization of the cluster phenomenon. Then the phase clustering model is combined with a local search algorithm to solve graph coloring problem. Secondly, we conduct in-depth research on the network game in the process of network dynamics, especially the prisoner’s dilemma game, and a detailed analysis of game data is given. Finally, combining the game dynamics with evolutionary algorithms and the proposed mobile operator for network reconstruction. The main contents of this paper are as follows:1. A hybrid algorithm of graph coloring based on phrase clustering model. In this paper, we mainly combine the principle of the classical phase clustering model with the theory of complement graph in graph theory, which makes the phases of neighboring nodes get closer and the phases of non-adjacent nodes become further away, in order to achieve the purpose of initial grouping. Furthermore, a local search algorithm- bucket sort is introduced to correct the misclassified nodes in the initial classification results, so as to improve the accuracy of the algorithm. Experiments show that as long as the parameters of network evolution are set reasonable, the algorithm has a good clustering effect, and can get the right result along with optimal number of coloring.2. Analyses of game dynamics and game data. In this paper, on the basis of understanding the game dynamics, the classic prisoner’s dilemma game is connected with the problem of network reconstruction. Then, the specific game data is analyzed from the theoretical point of view. The problem that under what circumstances the game date are enough to reconstruct the whole network can be explained, and the problem that under what circumstances the game date can only reconstruct part of the network edges becomes clear.3. Network reconstruction based on game dynamics. In the field of complex networks and systems biology, experts and scholars have presented large numbers of heuristic algorithms for network reconstruction based on the observation data. In this article, we combine the prisoner’s dilemma game theory with evolutionary algorithm to reconstruct the topology of the network. The reconstructive sequences of the nodes are in accordance with their degrees from small to large one by one during reconstructing. Firstly, the method produces some approximate solutions through evolution iteration, and moving operator is introduced on this basis. Secondly, moving operator is used to expand the approximate solutions so that the correct solution of the problem is achieved. Finally, the only solution is obtained after shrinking the extended data set by the game data. Experiments show that the proposed algorithm has an very good effect on the reconstruction of the network.