Research On Dynamic Process Problems In Complex Networks

In recent years, complex networks as a new perspective for studying complex systems, focus on the topologies formed by interactions between individuals in the system, which is a basis of understanding the features and functions of complex systems. Complex networks research common properties among all kinds of networks with different manifestations and universal methods which deal with these properties. After Watts and Strogatz proposed a small-world model in 1998, and Barabasi and Albert gave a scale-free model, complex networks are in a period of high-speed development, which is even called the new science of networks. Currently, complex networks have widely crossed with Mathematics, Physics, Computer and Information Science, Biology, Systems Science, Social Science and other disciplines, which have aroused great attention and popular participation of the researchers from different fields. Understanding the qualitative and quantitative characteristics of complex networks has become a common and challenging task of scientific research. The results from complex networks have a forward-looking, inspiring, instructive, promotive meaning for exploring other subjects and it will have broad application prospects.The key contents of complex networks include that find out statistical features of network structure, build suitable models for revealing the reasons of network evolution, and analyze the dynamical processes on networks in order to improve network performance and present effective methods of network design. This dissertation does some researches on dynamic process problems of complex networks and the results are as follow:Firstly, cascading failure will result in severe influence on Internet and power grid. It is a key to design rational load-capacity models against cascading failure for the sake of obtaining higher network robustness and lower cost. Based on related works, a load-capacity non-linear model was proposed, which is more suitable for real networks. The simulation was executed on BA scale-free network, ER random network, Internet AS level network, and power grid of western United States. The results show that the model is feasible and negative exponential relationship is found between the model's two parameters under certain conditions. Considering network cost and robustness, it is validated that the model can defense cascading failure better and investment costs are smaller in case of obtaining higher robustness than ML model.Secondly, in nature, congestion happens when network load exceeds its capacity of resource storage and process. For controlling congestion and improving transport efficiency, current researches focus on two aspects:modifying network structure and developing routing strategies. The latter is more concerned by people. Based on related works, we set up network node's model with different processing ability and capacity, proposed a traffic-awareness routing strategy with tunable control parameter. The best parameter of the routing strategy is decided by simulation and the obtained critical threshold of phase transition is consistent with theoretical estimation. The result shows that the routing strategy can improve the efficiency of network transmission better than other strategies. At the same time, we find that different processing ability of network nodes determines the critical threshold of phrase transition.Thirdly, influence spread is one of key problems about dynamic process problems on complex networks, and the research results of influence maximization problem based on dynamic networks are less. We discuss dynamic independent cascade model and dynamic linear threshold model and propose a dynamic influence maximization problem based on above two models. Then, we present an improved greedy algorithm, which eliminates the uncertainty of stochastic models and improves its performance by using connected graph approach. The algorithm is validated on four datasets with different sizes including AS, EMAIL, DELICIOUS and DBLP. The results show that, compared with HT algorithm the size of influence spread of our algorithm has an obvious advantage, and time efficiency is better than the HT algorithm.Finally, we try to analyze the features of structure evolution of the network by complex networks. We classify the network by using role-to-role connectivity profiles and find that social networks belong to stringy-periphery class. We confirm that the network has these properties, such as free-scale distribution, densification law and shrinking diameter. We observe that the community size in the network obeys the power-law distribution and many middle communities are composed of stars. We also discover there is core structure with high connectivity in the network. We research the evolution of community structure based on event framework and reveal that the community merge depends largely on the clustering coefficient of the graph composed of nodes which are directly connected between communities and the community split is related to its clustering coefficient.