复杂网络中随机图模型研究  

Research on the model of random graphs in complex networks

作　　者：黄斌[1] 吴春旺[2] 郑丰华[3] 蔺冰[2] 

机构地区：[1]成都信息工程学院数学学院,四川成都610225 [2]成都信息工程学院网络工程学院,四川成都610225 [3]成都信息工程学院计算中心和网络舆情研究所,四川成都610225

出　　处：《计算机工程与科学》2014年第7期1377-1383,共7页Computer Engineering & Science

基　　金：成都信息工程学院中青年学术带头人科研基金资助项目(J201218)

摘　　要：随着复杂网络研究的兴起,随机图成为一种重要复杂网络模型。基于完全图的生成子图的思想,得到了生成随机图的一种新算法,即用去边的方法生成随机图的算法,并用数值实验验证了加边和去边生成的随机图的统计特性(最大度、最小度、聚集系数、平均最短路径和平均度)是相近的,用去边的方法得到的图的度分布曲线在其平均度处达到峰值,随后呈指数下降,这与随机图的度分布是相同的。为了得到稀疏连通的随机图,又提出了一个不去割边的近似随机图生成算法,并从理论上说明了该算法生成的图是连通的,同时通过数值实验验证了图的连通性,并与加边随机图的统计特性进行了比较。With the development of the study of complex networks, random graphs become an important model in complex networks. On the basis of spanned subgraphs of complete graphs, a new algorithm of generating random graphs is proposed by means of removing the edges of a complete graph. It is verified by numerical experiments that the statistical properties （maximum degree, minimum degree, clustering coefficient, average shortest path and the average degree） of the random graphs generated by increasing or removing the edges are similar to each other. The degree distribution of these graphs ob- tained by removing edges reaches the peak at the average degree and then turns to decay exponentially. This is the same as the degree distribution of random graphs. In order to get the sparse connective ran- dom graphs, an approximate random graph generation algorithm without removing cutting edge is pro- posed. And it is theoretically explained that the generated graphs are connected ones. Meanwhile, nu- merical experiments are carried out to verify that the generated graphs are connected, and the comparison of statistical properties is made with the random graphs generated by increasing the edges.

关 键 词：随机图 完全图 生成子图 复杂网络 连通性 算法 

分 类 号：N941.9[自然科学总论—系统科学]