Measurements and Evolution of Complex Networks with Propagation Dynamics

Abstract

With the development of technology, we live in a world which is surrounded by complex networks, e.g., the power grid, transportation network, Internet, neural networks, social networks. Understanding the structure and dynamics of these extremely complex interactive networks has become one of the key research topics and challenges of life science in the 21st century. For example, the coronavirus disease 2019 (COVID-19) pandemic markedly changed human mobility patterns, hygienic habits and the communication methods. In order to control the virus spread, it is very necessary to analyze the network structures and epidemic dynamics, e.g., the importance of nodes in the networks, the influence of network structure measurements on propagation, the interaction between propagation dynamics and the structure measurements, and the construction of epidemiological models that can capture the effects of these changes in mobility on the spread of virus. Meanwhile, the results of these studies can also be used as a reference for the study of multiple propagation behaviors in other networks.

Complex network theory is to study the commonness of these seemingly different complex networks and the universal methods to deal with them. In 1998 and 1999, the finding of small world effects and scale-free property has attracted a great deal of attention of network structures and dynamics, which raises the science awareness for the real world. After the discovery of small world effects and scale-free property of networks, researchers gradually realize and study the complexity of networks. More network structure metrics are proposed, and more network characteristics are found with the development of complex network research. For example, many networks have community structures, e.g., the families, the schools, in which the internal connection of the community is much closer than the external connection. Meanwhile, studies on network structure related to the structure metrics are also in progress, such as the node influence identification, the community structure mining and the link prediction.

As one of the main subjects in the field of complex network theory, the study on dynamical behaviors in complex networks has assumed greater importance and attracted wider attention since the spreading phenomena on different type of real-world networks affect significantly human activities in social and economic environments. For example, the epidemic spread in the crowd, the cascading failures in the power grid and the information diffusion in online social networks. It is pointed out that the network structure measurements have an important impact on the propagation processes. For example, the epidemic threshold tends to zero in scale-free networks, which means that the virus is very easy to spread in scale-free networks because of a small minority of ‘super-spreader’. Compared with the scalefree network, the epidemic in the small world network is more difficult to break out due to the existence of the non-zero epidemic threshold.

While the network structure affects the propagation dynamics, the spreading process is also changing the network structure. For example, when a virus breaks out, people will selectively avoid symptomatic infected persons to protect themselves. The network structure has been changing dynamically due to the evasive behaviors, and the dynamic change in structure can also affect the spread of the virus in turn. In short, the network structure and the propagation dynamics in the network are coevolving.

In the thesis, the influence of complex network structure measurements on the propagation processes and the dynamic relationship between network structures and the propagation processes are studied. Firstly, the influence of network structure measurement on the propagation process is studied and applied to the process of node influence identification, cascading failure and virus propagation.