自增长网络模型及其算法  

A novel self-growing network model and its algorithm

作　　者：张志昌[1] 姚东任 刘霞[2] 

机构地区：[1]西北师范大学计算机科学与工程学院,甘肃兰州730070 [2]西北师范大学数学与统计学院,甘肃兰州730070

出　　处：《计算机工程与科学》2015年第7期1284-1289,共6页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(61163039;61163036;61363058);西北师范大学青年教师科研能力提升计划资助项目(NWNU-LKQN-10-2)

摘　　要：众所周知,现实世界的网络大部分都不是随机网络,少数的节点往往拥有大量的连接,而大多数的节点连接却很少,这正是无标度网络的重要特性。于是对于无标度网络性质的研究,因为其实用性而变得及其重要。首先定义了一种新的自增长网络模型,对它的基本参数进行计算,证明了它的无标度性。其次验证模型的最大叶子生成树的度分布服从幂率分布,并且得到了网络的平衡集,从而对无标度网络有了初步探索。最后给出了一个计算平均路长的算法。As is well known,most real world networks are not random networks. A few nodes usually have a lot of links while most nodes have few, and it is an important characteristic of scale-free networks, which is an important research topic. In this paper we firstly define a new type of self-growing network model, calculate its basic parameters, and validate its scale-free feature. We then prove that the degree distribution of the spanning tree with maximum leaves obeys the power law distribution and we get the balanced set of the network. Through those behaviors, we have a preliminary exploration on scale-free networks. Finally we propose an algorithm to calculate the average path length.

关 键 词：自增长网络 复杂网络 生成树 无标度网络 平衡集 

分 类 号：O157.5[理学—数学]