一种星–树结构的确定性的小世界网络

在过去的的几十年，人们运用各种机制建构了许多不确定性的和确定性的小世界网络。最近，郭世泽等人[1]通过在星图K1,2上运用一个简单的算法在每个迭代步添加一些边首次形成了一个二叉树结构的确定性的小世界网络。本文通过一个星图K1,6在每个迭代步连接每个树的各祖父节点和它的四个孙子节点，由此构建一个二叉树结构的新的确定性的小世界网络模型。此外，我们给出了一些拓扑属性的分析结果，它表明构建的模型是小世界网络。

小世界网络描述了许多现实世界网络，如神经网络、交通运输系统、生物和化学系统、社会网络、Internet 和WWW。通常地，小世界网络由三个主要的属性来描述：第一，它的平均路径长度随节点的数目对数增长，而不是随网络的规模线性地增长；第二，网络的平均节点度比较小；第三，网络有一个比较高的聚类[2]。

学者们提出了许多描述现实世界小世界网络的模型。

1998 年， Watts 和Strogatz[2]提出了首个小世界网络(WS 模型)，它改进了小世界网络特性的许多研究。Newman 和Watts[3] [4]更进一步提出了另一个小世界网络(NW 模型)。这两个经典的小世界模型都源于相同的规则环网。给定一个确定的重连概率，WS模型重连每一条边，而NW 模型在未连接的节点对间添加新边。1999 年，Kasturirangan 提出了一个对WS 模型可选择的小世界网络模型[5]，这个模型也始于一个环网，在环网中间添加一些节点，随机地连接到主环网中的度数大的节点。此外，为了研究小世界网络的其它形成机制，Ozik、Hunt 和Ott 引入了一个形成小世界网络的简单的进化模型，它是连接网络上的邻近节点[6]。

由于以上的小世界模型基于一定的概率规则连接系统中已存在的节点和新节点，因此它们都是随机的，我们不能形象地理解网络是如何形成的。为了计算、分析拓扑特性，许多学者用一些确定的方式构建无标度网络或小世界网络。

Comellas 等人[7]提出了第一个确定性的小世界网络。Boettcher 等人[8]基于著名的Hanoi 塔问题构建了一类确定性的小世界网络。

然而， 以上模型中节点数在产生过程中是固定的。

基于以上的模型， 许多其它类型的确定性的小世界模型被提出， 比如基于prime 数的[9] [10]， 基于Cayley图的[11]。

近来，郭世泽等人[1]提出的一个确定性的小世界网络模型，它是在星图K1,2 的每对兄弟节点及每个祖父节点和它的四个孙子节点之间连边构建一个二叉树结构实现的。本文的目标是由星–二叉树通过一个简单的机制在每个迭代步添加一些边形成一个确定性的小世界模型，它的聚集系数比较高。

2. 确定性小世界网络的构建 在大多数现实网络中，节点数目经常随时间步指数增长。因此，我们在星图1,6K的每个叶节点附着一个二叉树得到了一个新树，它的节点数随着层数指数增长，我们称之为星–二叉树。然而，由于树中没有三角形，因此它的聚集系数等于0。为了得到比较高的聚集系数，这里我们提出一个在每个迭代步基于一个简单机制添加边的产生算法。假设t 步后得到的网络为tSW ，它的节点数为tN ， 边数为tE ，其中0,1,2, , 1, tTT=−是迭代次数。假设每个节点标上一个随产生时间增加的自然数，