一类四正则小世界网络的生成树数目的算法

生成树是表征网络结构性质的一个重要物理量，然而精确地确定网络上的生成树数目是一个巨大的理论挑战。本文提出了一个四正则小世界网络模型。介绍了其概念及演化过程，详细计算了四正则图的相关拓扑特性，例如直径、聚类系数等。给出了此类四正则网络的生成树数目计算方法，得出生成树数目公式及熵。研究发现，所研究网络的生成树的熵与具有相同平均度的其他网络形成了鲜明的对比，因为后者的生成树的熵小于所研究网络。因此，这一四正则小世界网络上的生成树数目比其他具有自相似结构网络生成树的数目要多。

复杂网络已成为学术界研究的一个热点，许多现实世界中的网络都具有小世界效应，例如：电力网络、生物网络、交通网络、社会关系网络。一个网络具有小世界效应是指该网络具有较小的平均路径长度和较大的聚类系数这两个主要的属性，这里较小的平均路径长度是指网络的平均路径长度按照网络的阶的对数形式增长。

作为网络的另外一个重要的结构性质，网络中生成树数目的计算在数学、物理和其他学科里是一个基本的问题。生成树与网络的诸多方面有着紧密的联系[1] [2]，包括可靠性[3]、最优同步[4]、运输[5]、随机游走[6] [7]等。例如：一个网络的生成树数目与网络中两个节点之间的有效电阻密切相关[8]，并且还可以反过来决定两节点之间的平均首达时间；作为随机游走的一个基本量，生成树数目在不同理论和应用领域都有广泛的应用。另一方面，对于一个连通网络，在保持节点数不变的情况下，其生成树数目最大的结构网络具有最好的同步能力。最近，网络中的生成树一直是许多研究关注的焦点。许多文章中已经研究了特定网络中生成树数目，例如，Sierpinski 网络[9]，E-R 随机图[10]以及章忠志等人给出的分形无标度网络[2]，伪分形无标度网络[11]，小世界法雷网络[12]，在2013 年，作为所提出的计算生成树数目的新方法的算例，赵海兴等人计算出了文献[13] [14]中的模型的生成树数目.这些研究说明了不同网络结构中的生成树有不同的影响。

本文提出了一类具有小世界现象的四正则网络并且得到了其相应的拓扑特性， 例如直径、聚类系数。

结果表明我们的模型具有离散指数度分布、高聚类系数、较小的直径，满足小世界网络的主要特性；给出了此类四正则网络的生成树数目的计算方法并得到了相应的公式， 根据生成树数目确定了生成树的熵。

2. 网络生成的迭代算法 正则图是每个顶点的度相同的图[15]。若每个顶点的度均为k ，称为k -正则图。通过迭代的方法构造了一类四正则图。

为了正确计算tG 的生成树数目， 首先构建一个新模型tF 如图1、2 所示， 用()0tF t ≥来表示经过t 步后的网络，网络tF 的生成算法如下：当0t =时的初始网络tF 是一个四个节点连接三条边的三叉树， 当1t = 时网络tF 是由两个三叉树粘贴而成， 使得最底层的每个叶子节点的度为4， 对于2t ≥，tF通过如下的方式得到：对1tF −中在1t −步生成的三叉树的每个叶子节点再生出三个叶子节点， 然后复制这个三叉树，粘贴这两个三叉树的最底层叶子节点并使得它们的度为4(如图1)。计算得到了网络tF 的总