The Research On Reconstruction And Controllability Of Complex Networks

The reconstruction and controllability of complex networks are both hot issues of current research. The reconstruction of complex networks aims at mining connections between nodes and inferring the network topology from the dynamical characteristics of nodes, while the network structure is a basis for understanding and controlling complex networked systems. The controllability is a basic prob-lem of controlling networks, which is closely related to the topological structure of networks. This dissertation conducts the study of several problems in the re-construction and controllability of complex networks. The main results of this dissertation include the following three aspects:1. Global and partitioned reconstructions of undirected complex networks:In view of the issues regarding cost of measurement and timeliness of predicting, it is necessary to improve the prediction efficiency. It is also a significant challenge to predict the network topology from a small amount of dynamical observations. Different from the usual framework of the node-based reconstruction, two optimiza-tion approaches (i.e., the global and partitioned reconstructions) are proposed to infer the structure of networks from dynamics. The global reconstruction (GR) considers all nodes as a whole, and the partitioned reconstruction (PR) considers nodes in groups. These two approaches are helpful to mine the hidden information and make full use of it. Taking the two representative evolutionary games (includ-ing the prisoner’s dilemma game and the snowdrift game dynamics) occurring on different networks for example, the GR and the PR are realized for undirected net-works via compressed sensing. The results show that, no matter the networks are homogeneous or heterogeneous, these two approaches can more efficiently achieve higher reconstruction accuracy with relatively small amounts of data. The GR and PR approaches are not confined to undirected networks, and their ideas have a cer-tain universality. These two approaches provide different perspectives on effectively reconstructing complex networks from collective dynamics.2. Analytical results of controllability of deterministic bipartite networks:Ac-cording to the exact controllability theory, a further analysis is made on the con-trollability of bipartite graphs and elementary transformations of identifying driver nodes. Based on this, the controllability is investigated analytically for two typi-cal types of self-similar bipartite networks, i.e., the classic deterministic scale-free networks and Cay ley trees. Due to their self-similarity, the analytical results of the exact controllability are obtained, and all possible minimum sets of driver nodes are also identified by elementary transformations on adjacency matrices. For these two types of undirected networks, it is revealed that the low-degree nodes are more likely to become the driver nodes; no matter the links are unweighted or (nonzero) weighted, the controllability of networks and the configuration of driver nodes remain the same, showing a robustness to the link weights. These results have implications for the control of real networked systems with self-similarity.3. Effect of degree correlations on controllability of undirected networks:The controllability of a complex network is not only related to the degree distribution of the network, but also affected by the degree correlation whose effect, however, still remains unclear for an undirected network. Simulated annealing algorithm is used to change the network degree correlation coefficient by link rewiring, which makes it feasible to explore the relationship between the network controllability and degree correlation. Numerical simulations show that the density of driver nodes (controllability measure) for undirected networks decreases monotonically with the increase of the degree correlation coefficient under constant degree distribution. Further studies show that bidirectional networks and some directed networks also follow this rule. The increase of the degree correlation coefficient in undirected networks implies that all kinds of degree correlation coefficients in the corresponding directed networks also increase, but the effect of these compre-hensive changes on the network controllability can not be simply attributed to the accumulation of different results in the corresponding directed networks. Some explanations are given for this phenomenon, including the theoretical analysis when the degree correlation coefficient is around 0. Although an undirected network can be regarded as a special case of a directed network, the effect of the degree correlation on the controllability in an undirected network has a special rule, which can not be directly reflected or simply derived by the effect in the directed network. At the same time, it is verified that for a large sparse network without self-loops, no matter the network is assortative or disassortative, its structural controllability is still consistent with its exact controllability. Moreover, it is found by numerical simulations that the clustering coefficient has no obvious influence on the controllability of the undirected network. These studies will help the understanding of the relationship between the network controllability and the network structure.