The Clustering Coefficients In Random Graph Models

In chapter one,we introduce the concept of random graph and the three common random graph models of complex networks and their properties.In late 1950 s,Erd ?os and R?enyi put forward the classical random graphs(ER graphs)based on classical graph theory,in which edges are generated randomly,and also study some essential qualities such as the problem of the exist of the giant component.However,the researchers found that the ER model can't describe the real networks completely.For example,the real networks is not entirely random,the real networks are small world and the degree distribution of power law properties have not been explained in the ER model.With the theory of random graph more and more improved and perfect,In 1990 s,the small-world model and the scale-free model proposed to make up the defects of the ER model,and can generate complex networks with some properties.In this chapter,we overview the small-world model and the scale-free model.Most of the real networks are very complex,but they have three common characteristics:power law distribution,small average shortest path length and large clustering coefficient.Small average shortest path length and large clustering coefficient are common factors in small-world model.At the end of this chapter,we list the definition of the clustering coefficient and the average shortest path length in detail.In chapter two,the global clustering coefficient and the average clustering coefficient's convergence properties of the ER graph are analyzed.The results show that when the size of the graph is appropriately large,the convergence is uniform.In addition,at the end of the chapter,the average shortest path length's numerical simulation is also given.All this show that ER random graph does not belong to small-world models.In chapter three and four,we introduce the backgrounds and models of the threshold graphs and the geographical threshold graphs.But in the threshold graphs and geographical threshold graphs,we can hardly give the convergence properties of the average clustering coefficient in theory because of the non-independence of the edges,and only give the convergence properties of the global clustering coefficient.At the same time,the numerical simulation of the average clustering coefficient,the global clustering coefficient and the average shortest distance is given,and also the discussions.In addition,the threshold graphs and geographic threshold graphs' structure characteristics depends on the threshold parameter.We give the average clustering coefficient and global clustering coefficient with threshold parameters numerical simulation and discusses the small-world properties in the threshold graphs and geographic threshold graph.And the threshold graphs and the geographical threshold graphs models are regarded as the small-word model when the parameter ? is chosen properly.All the numerical simulations are based on the weights chosen from uniform distribution.In chapter five,we forecast the almost surely convergence of the global clustering coefficient and the convergence of the average shortest path length in probability in ER random graphs,the threshold graphs and the geographical graphs.