一种确定性小世界网络模型平均路径长度的逼近方法  

An Approximation Algorithm for Average Path Length in A Small-World Network Model

作　　者：张科 赵海兴[2] 李峰[2] 

机构地区：[1]青海师范大学数学系,西宁 [2]青海师范大学计算机学院,西宁

出　　处：《应用数学进展》2014年第1期22-28,共7页Advances in Applied Mathematics

基　　金：科技部973专项(No.2010CB334708);国家自然基金项目(No.61164005);教育部长江学者与创新团队支持计划(No.IRT1068);青海省自然基金项目(No.2012-Z-943)。

摘　　要：确定性小世界网络是复杂网络中的一个重要的研究分支。2008年,章忠志等人(Eur.Phys.J.B 63)在复杂网络的视角下对确定性均匀递归树作了详尽地分析,得到了其拓扑属性。尽管确定性均匀递归树的平均路径长度表现出了网络大小的对数规模,但是它的聚类系数为零。2012年,陆哲明等人(Physica A 391)通过在确定性均匀递归树的基础上以一个简单的规则添加一些边得到一个确定性小世界网络模型。本文根据网络模型的结构用分析的方法给出了文献Physica A 391中的模型的平均路径长度的逼近方法。Deterministic small-world network is an important branch of study of complex networks. In 2008, Zhang et al. in Eur.Phys.J.B 63 have offered detailed topological characteristics of the deterministic uniform recursive tree from the viewpoint of complex network. They derived topological characteristics of the deterministic uniform recursive tree. It shows a logarithmic scaling with the size of the network, however, its clustering coefficient is zero. In 2012, Lu, et al. in Physica A 391, based on the deterministic uniform recursive tree, by a simple rule to add some edges, got a deterministic small-world network model. In this paper, using an approximation algorithm based on the network construction, we show explicitly the average path length of the model constructed in Physica A 391.

关 键 词：图论 平均路径长度 小世界网络 

分 类 号：F2[经济管理—国民经济]