Research On Convergence Of Degree Distribution Of Evolving Networks

In real life,there are lots of complex networks,for example,communication network,biological network,power network and social network,etc.The study of complex network has been in the phase of vigorous development,its researchers come from the fields of physics,mathematics,social networks,infectious diseases and so on.Starting from the end of the 20 th century,with the small-world model and scale-free network being proposed,the enthusiasm of the scientific community to study complex networks has bee greatly stimulated.People began to explore the formation mechanism and organizational principles behind these networks,that is,the topological characteristics of complex networks.How to establish the theoretical basis of evolving networks has gradually attracted widespread attention,especially the connectivity of networks in limiting,clustering and degree distribution.Among them,the degree distribution plays a very important role.Research on degree distribution in existing literatures mainly focuses on the calculation of steady state degree distribution in different kinds of networks,but on convergence of degree distribution has gained little attention.In reality,people pay attention to the gap between the degree distribution and the steady state degree distribution after the network evolves to a certain time,if there is a great difference between the degree distribution and steady tate distribution,the any conclusions from the obtained network may be erroneous.Therefore,it is necessary to prove the convergence of the degree distribution in theory.The sample space changes with time make it hard to explore the convergence of degree distribution for complex networks.For the traditional method,we can use the same dimension vectors to represent the degree distribution of each network in the evolution process.Thus,a homogeneous Markov chain with degree distribution can be constructed.Its transition probability matrix is the transition probability matrix from network to network.This method is feasible in theory,there are still some problems in practical research.The reason is that when the network evolves to a large scale,its degree distribution state space will be very complex and it is difficult to determine each state.In this paper,the convergence of average degree distribution for random birth-and-death networks with two walls is examined,we prove that the existence of stationary degree distribution is equivalent to the average degree distribution convergence in distribution.Then the convergence in probability and in mean square for average degree distribution of random birth-and-death networks with two walls are discussed.After that,we propose a stochastic process rules(SPR)based Markov chain method.We first restructure the networks' evolving rules while maintaining their topological structures and statistical characteristics.The purpose of restructuring here is to keep all nodes in one set during the whole evolving process,making it possible to study degree distributions of evolving networks in one sample space.Using this new approach,we calculate the degree distributions of growing exponential networks(GEN),the convergence of average degree distribution for GEN is examined,we prove that the existence of stationary degree distribution is equivalent to the average degree distribution convergence in distribution.Then the convergence in probability and in mean square for average degree distribution of GEN are discussed.Finally,the simulation results validate our conclusions.