本文選題：ER圖 + 閾值圖　； 參考：《吉林大學(xué)》2017年碩士論文

【摘要】：本文第一章介紹了隨機(jī)圖的概念和復(fù)雜網(wǎng)絡(luò)的三種常見隨機(jī)圖模型及其性質(zhì)。在20世紀(jì)50年代末期,Erd′os和R′enyi將邊生成的隨機(jī)性引入到經(jīng)典的圖論里面,提出了經(jīng)典的隨機(jī)圖模型  ER圖,并且研究了一些重要性質(zhì)例如極大元存在的閾值問題。但在實(shí)際生活中,研究者們發(fā)現(xiàn)ER圖模型不能完全刻畫現(xiàn)實(shí)網(wǎng)絡(luò)。比如現(xiàn)實(shí)網(wǎng)絡(luò)并非完全是隨機(jī)的,現(xiàn)實(shí)網(wǎng)絡(luò)的小世界性質(zhì)和度分布的冪規(guī)律性質(zhì)并沒有在ER圖里得到解釋。隨著隨機(jī)圖論的理論越來越完善,在20世紀(jì)90年代,小世界模型和無標(biāo)度模型的提出彌補(bǔ)了ER圖模型的缺陷,而且能夠生成符合某些性質(zhì)的復(fù)雜網(wǎng)絡(luò)。本章綜述了小世界模型和無標(biāo)度模型的提出、模型的建立和一些重要的結(jié)論,并給出了簡(jiǎn)單的例子。大多數(shù)的現(xiàn)實(shí)網(wǎng)絡(luò)是很復(fù)雜的,但是它們有著三個(gè)共性:冪律分布,平均最短距離小和聚類系數(shù)大。小的平均最短距離和大的聚類系數(shù)是小世界模型所共有的。我們?cè)敱M地總結(jié)了聚類系數(shù)和平均最短距離的定義。本文第二章分析了ER圖的全局聚類系數(shù)和平均聚類系數(shù)的收斂性質(zhì)。對(duì)于推廣的ER圖,我們給出了全局聚類系數(shù)的幾乎必然收斂和平均聚類系數(shù)的依概率收斂。結(jié)果表明在圖的規(guī)模適當(dāng)大時(shí),兩者收斂是一致的,而且從模擬結(jié)果可以看出幾乎處處和概率p相等。在結(jié)尾時(shí),還給出了平均最短距離的模擬。以上的兩點(diǎn)說明了ER圖不屬于小世界模型。本文第三章和第四章分別介紹了閾值圖和地理閾值圖的背景和模型。但在閾值圖和地理閾值圖模型中,由于邊形成的不獨(dú)立性,很難在理論上給出平均聚類系數(shù)的收斂性質(zhì),只給出了全局聚類系數(shù)的收斂性質(zhì),并同時(shí)給出了平均聚類系數(shù)和全局聚類系數(shù)以及平均最短距離的模擬及討論。另外,閾值圖和地理閾值圖模型的性質(zhì)取決于閾值參數(shù),我們給出了平均聚類系數(shù)和全局聚類系數(shù)隨著閾值參數(shù)變化的模擬并探討了閾值圖和地理閾值圖模型的小世界性質(zhì)。指出,選取適當(dāng)?shù)摩戎?閾值圖和地理閾值圖可以看做小世界模型。在模擬時(shí),權(quán)重服從(0,1)上的均勻分布。本文第五章,展望了ER圖、閾值圖和地理閾值圖的全局聚類系數(shù)的幾乎必然收斂和平均最短距離的收斂。
[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.
【學(xué)位授予單位】：吉林大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：O157.5

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 程婷婷;王恒山;劉建國(guó);;通用計(jì)算網(wǎng)絡(luò)圖聚類系數(shù)和環(huán)方法[J];計(jì)算機(jī)科學(xué);2011年11期

2 肖碧玉;李先彬;沈良忠;劉文斌;;比較圖元向量和點(diǎn)的聚類系數(shù)對(duì)差異網(wǎng)絡(luò)的研究[J];生物信息學(xué);2013年04期

3 胡明生;賈志娟;雷利利;洪流;;基于復(fù)雜網(wǎng)絡(luò)的災(zāi)害關(guān)聯(lián)建模與分析[J];計(jì)算機(jī)應(yīng)用研究;2013年08期

4 李岸巍;阮豫紅;;基于MATLAB環(huán)境的聚類系數(shù)的計(jì)算[J];山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年03期

5 李圓媛;;應(yīng)用SQL求邊的聚類系數(shù)[J];科技資訊;2013年07期

6 李圓媛;;應(yīng)用SQL求邊的聚類系數(shù)[J];黑龍江科技信息;2013年19期

7 付大愚;趙海;張君;葛新;;一種基于社團(tuán)結(jié)構(gòu)的局域復(fù)雜網(wǎng)絡(luò)模型[J];小型微型計(jì)算機(jī)系統(tǒng);2010年05期

8 羅聰;劉威;鄭曙光;;聚類系數(shù)對(duì)小世界交通網(wǎng)絡(luò)搜索路徑的影響[J];數(shù)字技術(shù)與應(yīng)用;2012年09期

9 王筱蕾;劉建華;;一種基于多因素的BA演化模型[J];計(jì)算機(jī)與數(shù)字工程;2014年06期

10 陳進(jìn)良;林中材;楊孔慶;;含權(quán)地理網(wǎng)格網(wǎng)絡(luò)的構(gòu)建及其逾滲行為[J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2012年04期

相關(guān)會(huì)議論文 前1條

1 羅黨;秦玉慧;;一種灰色屬性識(shí)別聚類方法[A];2006年灰色系統(tǒng)理論及其應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2006年

相關(guān)碩士學(xué)位論文 前6條

1 左燾;基于網(wǎng)絡(luò)結(jié)構(gòu)的病毒傳播分析[D];南京郵電大學(xué);2015年

2 齊一全;面向圖聚類特性的圖采樣算法研究[D];遼寧大學(xué);2016年

3 張亞輝;隨機(jī)圖模型的聚類系數(shù)極限的研究[D];吉林大學(xué);2017年

4 馮立雪;結(jié)合最大度與最小聚類系數(shù)的復(fù)雜網(wǎng)絡(luò)搜索策略研究[D];北京交通大學(xué);2011年

5 張波;復(fù)雜網(wǎng)絡(luò)的構(gòu)建及演化方式研究[D];吉林大學(xué);2014年

6 石憲;基于車輛運(yùn)動(dòng)復(fù)雜統(tǒng)計(jì)特性的數(shù)據(jù)分發(fā)算法研究[D];天津大學(xué);2016年

，

本文編號(hào)：1879920