Research On Robustness Of Topological Structure And Dynamics Of Complex Networks

The past decade has witnessed the development of the complex network theory which is an effective methodology for addressing the complex system. The complex network theory abstracts real complex systems as networks composed of edges and nodes. By investigations on the structural properties of the networks and the dynamics on the networks, deep insights into the complexity of the world have been obtained. Thus, complex network theory has attracted ample attention. The topological structure of a network has a huge impact on its function. The functions of a network are usually expressed through the dynamic processes on the network. The topological structure thus has an immense influence over the dynamic processes. Therefore, the study on the topological structure is the key to understanding complex networks. If the structure of a network is destroyed, the function of the network will be affected to some extent. The less a network is influenced by any sort of destruction, the more robust it is. Research on the robustness is helpful in constructing networks with robust and resilient structure. Also notable is that a node in a network often tends to adapt its neighborhood structure (promoting or suppressing) to the dynamic process on the network according to the circumstance it is in. The interplay between the adaptive behavior of the node and the dynamic process is referred to as co-evolution. How to exactly describe co-evolution is still a big challenge.This dissertation focuses on the topological structure and its robustness of complex networks, and the co-evolution phenomena. The main contributions of this dissertation are as follows:(1) Chapter3focuses on the edge betweenness as well as its properties which is one of the important topological characteristics. By means of generating function theory, we propose an exact formula for the expectation of betweenness of an edge in tree-like finite components (i.e. tree-like connected sub-graphs with finite sizes) of random graphs with arbitrary degree distributions and confirm it for Poisson and power law degree distribution graphs. We also find out that there exists a linear relation between the edge betweenness and the size of the finite component that the edge belongs to. Previously, less attention has been paid on the edge betweenness. The analytical work of this dissertation is thus of great importance. Besides, the proposed formula is capable of measuring exactly the payload of an edge and how dangerous it is to become jammed by real traffic.(2) Chapter4studies the change in the structure and function of a network suffering random failure in its structure. We analytically study the change of the average shortest path length of a random graph under random edge removal and propose a rather exact approximation formula for the change. We confirm the proposed formula for random graphs with Poisson, power law and exponential degree distributions. The proposed formula can offer a common framework for the research regarding the robustness of various random graphs and is helpful in constructing a network which could resist the influence of random failure.(3) Chapter5focuses on the co-evolution in finite-size networks and takes as example the interplay between the epidemic spread in a network of individuals and the topological adaptation behavior of individuals to the epidemic. We propose an adaptive SIS model (in short, ASIS model) which exactly describes the co-evolution in finite-size networks by means of the Markov process. We study the steady state behavior and derive exact solutions to the average meta-stable state infection fraction and the epidemic threshold. A linear law between the epidemic threshold and the rate of adaptation is found, which means the topological adaptation can suppress epidemic in a linear way. By simulations, we find out that the topological adaptation in response to epidemic spread promotes the network evolution towards a topology that exhibits assortativity and modularity. The topology consists of two loosely interconnected clusters with one composed of highly intra-connected susceptible nodes and the other composed of all infected nodes. Theoretically, the widely used mean field approximation method is not as exact as our proposed method in describing the co-evolution in finite-size networks because it ignores critical structural details. Our findings substantially help obtaining a better insight into the impact of the individual behavior over the epidemic spread and it is also of great importance to the research regarding the prevention of epidemic spread.