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

Spanning Trees in a Class of Five Regular Small World Network

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

Abstract: Spanning trees are an important quantity characterizing the reliability of a network, however, explicitly determining the number of spanning trees in networks is a theoretical challenge. In this paper, we present a class of five regular network model with small world phenomenon, and introduce the concept and evolving process. We determine the relevant topological characteristics of the five regular network, such as diameter, clustering coefficient. We give a calculation method of number of spanning trees in such five regular network and derive the formulas and the entropy of number of spanning trees. We find that the entropy of spanning trees in the studied network is in sharp contrast to other small world with the same average degree, the entropy of which is less than the studied network. Thus, the number of spanning trees in such five regular network is more than that of other self-similar networks.

1. 引言

复杂网络借助于图论和统计物理的一些方法，可以用来捕捉并描述系统的演化机制、演化规律(结构)和整体行为，成为了学术界研究的一个热点，许多现实世界中的网络都具有小世界效应例如电力网络、交通网络、生物网络、社会关系网络。一个网络具有小世界效应是指该网络具有较小的平均路径长度和较大的聚类系数这两个主要的属性，这里较小的平均路径长度是指网络的平均路径长度按照网络的阶的对数形式增长。

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

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

2. 网络生成的迭代算法

正则图是每个顶点的度相同的图 [13] 。若每个顶点的度均为 $k$ ，称为 $k$ -正则图。本文通过迭代的方法构造了一类五正则图。为了正确计算 $G_t$ 如图2所示的生成树数目，首先构建一个新模型 $F_t$ 如图1所示，用 $F_t\left(t\ge \text{0}\right)$ 来表示经过 $t$ 步后的网络，网络 $F_t$ 的生成算法如下：当 $t=0$ 时的初始网络 $F_t$ 是一个五个节点连接四条边的四叉树，当 $t=1$ 时网络 $F_t$ 是由两个四叉树粘贴而成，使得最底层的每个叶子节点的度为5，对于 $t\ge 2$ ， $F_t$ 通过如下的方式得到：对 $F_{t-1}$ 中在 $t-1$ 步生成的四叉树的每个叶子节点再生出四个叶子节点，然后复制这个四叉树，粘贴这两个四叉树的最底层叶子节点并使得它们的度为5 (如图1)。计算得到

Figure 1. Construction of $F_t$ , showing the first three steps of the iterative process

图1. $F_t$ 的前三步迭代构造

了网络 $F_t$ 的总点数 $N_t=4N_{t-1}+2=\frac{5\cdot 4^t-2}{3}\left(t\ge 1\right)$ 和总边数 $E_t=4E_{t-1}+8=\frac{50\cdot 4^{t-1}-8}{3}\left(t\ge 1\right)$ 。

本文所研究的五正则网络模型 $G_t$ 是由两条边连接两个 $F_t$ 构成的(如图2)。并计算得到了 $G_t$ 的总点数

${N^{\prime }}_t=2N_t=\frac{10\cdot 4^t-4}{3}\left(t\ge 1\right)$ 和总边数 ${E^{\prime }}_t=2E_t+2=\frac{100\cdot 4^{t-1}-10}{3}\left(t\ge 1\right)$ 。

3. 拓扑特性

3.1. 直径(Diameter)

直径指网络中所有节点对之间最小距离的最大值，它反映网络最大传递延迟的属性。小的直径与小世界网络的概念是一致的，这里用直径代替平均路径长度来说明网络的小世界特性。用 $D\left(t\right)$ 表示本网络模型的时间步 $t$ 时的直径。由图2知， $D\left(0\right)=\text{1}$ ， $D\left(1\right)=\text{3}$ ，在接下来的每一迭代步 $\left(t\ge 2\right)$ 中，直径随着新点的增加而增加。网络的直径满足公式：

$D\left(t\right)=2t+1$ .

用归纳法可证明公式成立。并且

$t~\frac{\ln N_t}{\ln 4}$ .

因此直径随着节点数的增加呈对数形式增长，因为平均路径长度小于直径 $D\left(t\right)$ ，并且平均路径长度比直径增加的更缓慢，所以该五正则网络满足小世界网络特性。

3.2. 聚类系数(Clustering Coefficient)

聚类系数是用来衡量一个复杂网络的集团化程度，它是网络的另一个重要特征参数。节点 $i$ 的聚集系数 $C_i$ 描述的是网络中与该节点直接相连的节点之间的连接关系，即与该节点直接相邻的节点间实际存

在的边数目占最大可能存在的边数的比例， $C_i$ 的表达式为 $C_i=\frac{2e_i}{k_i\left(k_i-1\right)}$ ，式中 $k_i$ 表示节点 $i$ 的度， $e_i$ 表

示节点 $i$ 的邻接节点之间实际存在的边数。网络的聚集系数 $C$ 为所有节点聚集系数的算术平均值，即

$C=\frac{\text{1}}{N}{\displaystyle {\sum }_{i=1}^N{C}_i}$ ，其中 $N$ 为网络的阶。计算的详细过程如下：

Figure 2. Construction of $G_t$ , showing the first three steps of the iterative process

图2. $G_t$ 的前三步迭代构造

在 $t=0$ 步， $C=\text{1}$ 。在接下来的每一步 $t\ge 1$ ，都有

$C=\frac{\text{9}\cdot {\text{4}}^t}{50\cdot {\text{4}}^{t\text{-}1}-5}$ .

显然，当 $t\to \infty$ 时， $C\approx \text{0}\text{.72}$ ，具有较高的聚类系数，满足小世界特性。

4. 生成树数目(Spanning Trees)

生成树 $T$ 是一个连通图 $G$ 的一个极小连通子图，包含 $G$ 的所有 $n$ 个顶点，有 $n-1$ 条边的连通图。若 $T$ 为森林，则称它为 $G$ 的一个生成森林。我们找出了 $F_t$ 和 $G_t$ 的关系(如图3)。假设 $ST\left(F_t\right)$ 表示在 $F_t$ 中第 $t$ 步时的生成树数目， $SF\left(F_t\right)$ 表示在 $F_t$ 中第 $t$ 步时具有两个分支的生成森林数目，那么通过计算 $F_t$ 的生成树数目来求得原模型 $G_t$ 的生成树数目，他们的关系如公式(1)：

$ST\left(G_t\right)=2S{T}^2\left(F_t\right)+2ST\left(F_t\right)\cdot SF\left(F_t\right)$ (1)

由图3和图4容易看出 $F_t$ 在第 $t$ 步时的生成树数目是通过迭代的方法由 $t-1$ 步得到的，并且 $t$ 步的生成树是由 $t-1$ 步生成树和生成森林共同构成的， $F_t$ 有以下几种情形：

由图5可以看出 $F_t$ 的包含两个分支的生成森林有以下几种情形：

$\{\begin{array}{l}ST\left(F_t\right)=32S{T}^4\left(F_{t-1}\right)+48S{T}^3\left(F_{t-1}\right)\cdot SF\left(F_{t-1}\right)+24S{T}^2\left(F_{t-1}\right)\cdot S{F}^2\left(F_{t-1}\right)\\ +4ST\left(F_{t-1}\right)\cdot S{F}^3\left(F_{t-1}\right)\\ SF\left(F_t\right)=16S{T}^4\left(F_{t-1}\right)+32S{T}^3\left(F_{t-1}\right)\cdot SF\left(F_{t-1}\right)+12S{T}^2\left(F_{t-1}\right)\cdot S{F}^2\left(F_{t-1}\right)\\ +8ST\left(F_{t-1}\right)\cdot S{F}^3\left(F_{t-1}\right)+S{F}^4\left(F_{t-1}\right)\end{array}$ (2)

其中： $ST\left(F_0\right)=1,SF\left(F_0\right)=4$

令

因此可得

Figure 3. The network model $F_t$ and $G_t$ at step $t$

图3. $t$ 步时的网络 $F_t$ 和 $G_t$

Figure 4. The number of span ning trees of $F_t$

图4. $F_t$ 的生成树数目

Figure 5. The number of span ning forests with two components of $F_t$

图5. $F_t$ 中具有两个分支的生成森林数目

注意到 $SF\left(F_t\right)=\frac{4^t+5}{6\cdot 4^{t-1}}\cdot ST\left(F_t\right)$ ，代入(2)式得：

$ST\left(F_t\right)=4^{\frac{4^t-1}{3}}\cdot {{\displaystyle \underset{i=0}{\overset{t-1}{\prod }}\left(\frac{4^{t-i}+5}{6\cdot 4^{t-i-1}}+2\right)}}^{3\times 4^i}$ (3)

同理 $ST\left(F_t\right)=\frac{6\cdot 4^{t-1}}{4^t+5}\cdot SF\left(F_t\right)$ ，可得：

$SF\left(F_t\right)=4^{4^t}\cdot {{\displaystyle \underset{i=1}{\overset{t}{\prod }}\left(\frac{3\cdot 4^{t-i+1}}{4^{t-i+1}+2}+1\right)}}^{4^i}$ (4)

根据(3)，(4)式可推出公式(1)得到 $G_t$ 的生成树数目：

$\begin{array}{l}ST\left(G_t\right)=2ST\left(F_t\right)\left(ST\left(F_t\right)+SF\left(F_t\right)\right)\\ =2\times 4^{\frac{4^t-1}{3}}\cdot {{\displaystyle \underset{i=0}{\overset{t-1}{\prod }}\left(\frac{4^{t-i}+5}{6\cdot 4^{t-i-1}}+2\right)}}^{3\times 4^i}\cdot [4^{\frac{4^t-1}{3}}\cdot {{\displaystyle \underset{i=0}{\overset{t-1}{\prod }}\left(\frac{4^{t-i}+5}{6\cdot 4^{t-i-1}}+2\right)}}^{3\times 4^i}\end{array}$ $+4^{4^t}\cdot {{\displaystyle \underset{i=1}{\overset{t}{\prod }}\left(\frac{3\cdot 4^{t-i+1}}{4^{t-i+1}+2}+1\right)}}^{4^i}]$

则通过生成树数目计算出了 $G_t$ 的生成树的熵：

$E_{ST}\left(G_t\right)=\underset{t\to \infty }{\lim }\frac{\ln ST\left(G_t\right)}{N_t}\approx \ln 4\approx \text{1}\text{.386}$ .

$G_t$ 的生成树数目的熵与其他的网络进行比较。文献 [1] 中分形无标度网络的生成树的熵为1.0397，文献 [9] 中伪分形无标度网络的生成树的熵为0.8959，文献 [12] 中四正则网络的生成树的熵为1.099，对于方形格 [7] 和二维希尔宾斯基网络 [8] ，它们的生成树的熵分别是1.1662和1.0486，上面提出的网络都有是具有相同平均度4。文献 [10] 中平均度为5的网络的生成树的熵为1.2109，文献 [14] 中平均度为6的阿波罗网络的生成树的熵为1.354，它们都于小于1.386。因此，该小世界正则网络上的生成树数目比其他具有相同平均度网络的生成树的数目较大。这说明了两个网路生成树存在差别的主要原因在于它们的结构差异。

5. 总结

本文用迭代的方法构造了一类具有小世界效应的五正则网络模型，分析并得到了网络包括直径和聚类系数的主要拓扑特性。生成树作为网络结构性质的一个重要物理量，我们给出了此类五正则网络的生成树数目计算方法，得出生成树数目公式及熵。研究发现，所研究网络的生成树的熵与具有相同平均度的其他网络形成了鲜明的对比，这一五正则小世界网络上的生成树数目比其他具有自相似结构网络生成树的数目要多，也说明了不同网络之间的结构差异，我们给出的生成树数目的计算方法也可以应用到其他自相似网络上。

基金项目

国家自然基金项目(No. 11561056)、青海省自然科学基金项目(No.2016-ZJ-947Q)。