随机图模型的聚类系数极限的研究

发布时间：2018-05-12 19:49

本文选题：ER图 + 阈值图　；参考：《吉林大学》2017年硕士论文

【摘要】：本文第一章介绍了随机图的概念和复杂网络的三种常见随机图模型及其性质。在20世纪50年代末期,Erd′os和R′enyi将边生成的随机性引入到经典的图论里面,提出了经典的随机图模型 ER图,并且研究了一些重要性质例如极大元存在的阈值问题。但在实际生活中,研究者们发现ER图模型不能完全刻画现实网络。比如现实网络并非完全是随机的,现实网络的小世界性质和度分布的幂规律性质并没有在ER图里得到解释。随着随机图论的理论越来越完善,在20世纪90年代,小世界模型和无标度模型的提出弥补了ER图模型的缺陷,而且能够生成符合某些性质的复杂网络。本章综述了小世界模型和无标度模型的提出、模型的建立和一些重要的结论,并给出了简单的例子。大多数的现实网络是很复杂的,但是它们有着三个共性:幂律分布,平均最短距离小和聚类系数大。小的平均最短距离和大的聚类系数是小世界模型所共有的。我们详尽地总结了聚类系数和平均最短距离的定义。本文第二章分析了ER图的全局聚类系数和平均聚类系数的收敛性质。对于推广的ER图,我们给出了全局聚类系数的几乎必然收敛和平均聚类系数的依概率收敛。结果表明在图的规模适当大时,两者收敛是一致的,而且从模拟结果可以看出几乎处处和概率p相等。在结尾时,还给出了平均最短距离的模拟。以上的两点说明了ER图不属于小世界模型。本文第三章和第四章分别介绍了阈值图和地理阈值图的背景和模型。但在阈值图和地理阈值图模型中,由于边形成的不独立性,很难在理论上给出平均聚类系数的收敛性质,只给出了全局聚类系数的收敛性质,并同时给出了平均聚类系数和全局聚类系数以及平均最短距离的模拟及讨论。另外,阈值图和地理阈值图模型的性质取决于阈值参数,我们给出了平均聚类系数和全局聚类系数随着阈值参数变化的模拟并探讨了阈值图和地理阈值图模型的小世界性质。指出,选取适当的θ值,阈值图和地理阈值图可以看做小世界模型。在模拟时,权重服从(0,1)上的均匀分布。本文第五章,展望了ER图、阈值图和地理阈值图的全局聚类系数的几乎必然收敛和平均最短距离的收敛。
[Abstract]:In the first chapter, the concept of random graph and three common random graph models of complex network and their properties are introduced. In the late 1950s, Erdos and R'enyi introduced the randomness of edge generation into the classical graph theory, proposed a classical random graph model and studied some important properties, such as the threshold problem of the existence of maximal elements. But in real life, the researchers found that ER graph model can not completely depict the real network. For example, the real network is not completely random, the small-world property of the real network and the power law property of the degree distribution are not explained in the ER graph. With the theory of random graph becoming more and more perfect, in the 1990s, the small world model and scale-free model made up for the defects of ER graph model, and the complex network can be generated according to some properties. This chapter summarizes the small world model and scale-free model, the establishment of the model and some important conclusions, and gives a simple example. Most real networks are very complex, but they have three commonalities: power law distribution, small average shortest distance and large clustering coefficient. The small average shortest distance and large clustering coefficient are common to the small world model. The definitions of clustering coefficient and average shortest distance are summarized in detail. In the second chapter, the convergence properties of global clustering coefficients and average clustering coefficients of ER graphs are analyzed. For generalized ER graphs, we give the almost inevitable convergence of global clustering coefficients and the probability convergence of average clustering coefficients. The results show that the convergence of the two graphs is consistent when the scale of the graph is appropriate, and it can be seen from the simulation results that almost everywhere is equal to the probability p. At the end, the simulation of the average shortest distance is given. The above two points show that ER graph does not belong to the small world model. In the third and fourth chapters, the background and model of threshold map and geographical threshold graph are introduced respectively. However, in the threshold graph and geographical threshold graph model, it is difficult to give the convergence property of the average clustering coefficient in theory because of the independence of edge formation, but only the convergence property of the global clustering coefficient. At the same time, the simulation and discussion of average clustering coefficient, global clustering coefficient and average shortest distance are given. In addition, the properties of threshold map and geographical threshold graph model depend on threshold parameters. We give the simulation of average clustering coefficient and global clustering coefficient with threshold parameters and discuss the small-world properties of threshold map and geographical threshold graph model. It is pointed out that the threshold graph and the geographical threshold graph can be regarded as small-world model when the appropriate 胃 value is chosen. In the simulation, the weight of the uniform distribution from 0 to 1). In chapter 5, the convergence of the global clustering coefficients of ER graph, threshold graph and geographical threshold graph is predicted.
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】