计算机工程与科学
計算機工程與科學
계산궤공정여과학
COMPUTER ENGINEERING & SCIENCE
2014年
7期
1377-1383
,共7页
黄斌%吴春旺%郑丰华%蔺冰
黃斌%吳春旺%鄭豐華%藺冰
황빈%오춘왕%정봉화%린빙
随机图%完全图%生成子图%复杂网络%连通性%算法
隨機圖%完全圖%生成子圖%複雜網絡%連通性%算法
수궤도%완전도%생성자도%복잡망락%련통성%산법
random graph%complete graph%spanned subgraph%complex networks%connectivity%algorithm
随着复杂网络研究的兴起,随机图成为一种重要复杂网络模型.基于完全图的生成子图的思想,得到了生成随机图的一种新算法,即用去边的方法生成随机图的算法,并用数值实验验证了加边和去边生成的随机图的统计特性(最大度、最小度、聚集系数、平均最短路径和平均度)是相近的,用去边的方法得到的图的度分布曲线在其平均度处达到峰值,随后呈指数下降,这与随机图的度分布是相同的.为了得到稀疏连通的随机图,又提出了一个不去割边的近似随机图生成算法,并从理论上说明了该算法生成的图是连通的,同时通过数值实验验证了图的连通性,并与加边随机图的统计特性进行了比较.
隨著複雜網絡研究的興起,隨機圖成為一種重要複雜網絡模型.基于完全圖的生成子圖的思想,得到瞭生成隨機圖的一種新算法,即用去邊的方法生成隨機圖的算法,併用數值實驗驗證瞭加邊和去邊生成的隨機圖的統計特性(最大度、最小度、聚集繫數、平均最短路徑和平均度)是相近的,用去邊的方法得到的圖的度分佈麯線在其平均度處達到峰值,隨後呈指數下降,這與隨機圖的度分佈是相同的.為瞭得到稀疏連通的隨機圖,又提齣瞭一箇不去割邊的近似隨機圖生成算法,併從理論上說明瞭該算法生成的圖是連通的,同時通過數值實驗驗證瞭圖的連通性,併與加邊隨機圖的統計特性進行瞭比較.
수착복잡망락연구적흥기,수궤도성위일충중요복잡망락모형.기우완전도적생성자도적사상,득도료생성수궤도적일충신산법,즉용거변적방법생성수궤도적산법,병용수치실험험증료가변화거변생성적수궤도적통계특성(최대도、최소도、취집계수、평균최단로경화평균도)시상근적,용거변적방법득도적도적도분포곡선재기평균도처체도봉치,수후정지수하강,저여수궤도적도분포시상동적.위료득도희소련통적수궤도,우제출료일개불거할변적근사수궤도생성산법,병종이론상설명료해산법생성적도시련통적,동시통과수치실험험증료도적련통성,병여가변수궤도적통계특성진행료비교.
