一类网络拓扑性质的研究

Research on the Topological Properties of a Class of Networks

摘要: 当今社会，复杂网络无处不在，网络的拓扑特性与诸多有趣问题紧密联系，首先，介绍了一类环形网络的构造过程，接着，深入探究了这类网络的拓扑特性及其生成树的枚举问题。给出了这类网络的拓扑性质及其生成树数目公式的确解。在此基础上，进一步推导了这类网络进行边收缩后其变形网络的拓扑性质。最后，任意边赋权下该类环形网络的最小生成树问题，提出了一种算法，能够在任意条件下确定最小生成树的结构。在实际应用的背景下，研究了小规模该网络最小生成树的结构问题，采用Python进行了算法运行，验证了该算法的实用性与有效性，为实际应用提供了理论支持与实践依据。

Abstract: In today’s society, complex networks are ubiquitous, and the topological properties of networks are closely intertwined with many intriguing problems. Firstly, the construction process of a class of ring networks is introduced. Subsequently, the topological properties of this class of networks and the enumeration problem of their spanning trees are investigated in depth. The exact solutions for the topological properties of this class of networks and the formula for the number of spanning trees are derived. On this basis, the topological properties of the deformed networks obtained by edge contraction of this class of networks are further deduced. Finally, for the minimum spanning tree (MST) problem of this class of ring networks under arbitrary edge weight assignments, an algorithm is proposed, which is capable of determining the structure of the MST under any conditions. In the context of practical applications, the structural problem of the MST for small-scale networks of this type is studied, and the algorithm is implemented using Python. The practicability and effectiveness of the algorithm are verified, providing theoretical support and practical basis for real-world applications.

1. 引言

当今社会，复杂网络在我们生活中的应用已经变得十分广泛，例如：社交网络、交通网络、信息网络等[1]。目前，对于网络的研究已经从简单网络转向复杂网络的研究、从对随机的网络模型转向对小世界网络模型、无标度网络模型的研究[2]。同时，计算网络拓扑性质对于理解网络的动态过程有着深远影响，对于复杂网络结构的研究主要包含了节点的度分布[3]、聚类系数[4]和生成树的数目[5]等主要方面。1998年，Wattz和Strogatz [6]首次提出了小世界网络模型，得到结论该网络具有较高的聚类系数，为复杂网络的研究打开了大门，章忠志等人在对Sierpinski网络的研究中得到了该网络的拓扑性质的表达式，研究还发现此网络有着无标度、小世界等特性[7]。刘家保等人构建了一种具有金字塔结构的层次网络，探究了该网络的基本拓扑性质[8]。这些研究为理解复杂网络结构提供了深刻的理论基础。在网络的众多生成树中，最小生成树是最特殊的一种树形网络，它应用十分广泛，不仅在各个领域扮演着优化网络的关键角色，在数据分析、社会网络分析也发挥着重要作用。Haldane等人[9]通过构建了最小生成树与传染病传播网络进行类比来探究银行系统的脆弱性。孙博文等人在文献中研究了股市最小生成树的结构，发现了股市板块的内部存在着共振效应[10]。本文首先介绍了一类环形网络的构造过程，然后，深入分析了这类网络的拓扑特性及其生成树的枚举问题。给出了这类网络的拓扑性质及其生成树数目公式的确解。在此基础上，进一步推导了这类网络进行边收缩后其变形网络的拓扑性质。最后，本人所构造的网络$G_t$ 从结构上看，多个模块以循环方式衔接，各个模块之间由每个模块内部包含有序分层的节点，模块间通过$u_i$ 和$v_i$ 等节点实现了精准的交互作用，并且该网络适用于工程实践与自然系统等场景中。有着很大的研究价值和实际意义。本文分析了在任意边赋权下该类环形网络的最小生成树问题，提出了一种算法，能够在任意条件下确定最小生成树的结构。在实际应用的背景下，研究了小规模该网络最小生成树的结构问题，采用Python进行了算法运行，验证了该算法的实用性与有效性，为实际应用提供了理论支持与实践依据。

2. 网络模型及属性

为准确计算出环形网络$G_t$ 的拓扑性质，首先引入了一类确定性网络$F_t$ ，如图1所示。

其中，$t$ 表示网络的生成步数，$F_t$ 表示在第$t$ 步时所生成的网络，图中椭圆所标注的节点为该网络的中心节点，网络$F_t$ 生成过程描述如下：

(1) 当$t=0$ 时，$F_t$ 为一个四圈。

(2) 当$t=0$ 时，$F_t$ 是在$F_0$ 的基础上添加一个中心节点并与剩余两个节点相连。

(3) 当$t=1$ 时，$F_t$ 是在$t-1$ 步的基础上按照$t=1$ 时的迭代方法添加新的中心节点与剩余两个顶点连接得到，直至网络达到所需规模。

经简单计算得到网络$F_t$ 的节点数为：$N_t=t+4\left(t\ge 1\right)$ ，边数为$E_t=2t+4\left(t\ge 1\right)$ 。

本文研究的环形网络$G_t$ 由$m$ 条连接边连接$m$ 个子网络$F_t$ 所构成，如图2所示。

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

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

Figure 2. The network model of $G_t$

图2. 网络$G_t$ 结构

计算得$G_t$ 的节点数为${N^{\prime }}_t=m\left(t+4\right)\left(t\ge 1\right)$ ，边数为${E^{\prime }}_t=m\left(2t+5\right)\left(t\ge 1\right)$ 。

3. 网络G_t的拓扑性质

3.1. 直径

直径是任意两个顶点间最小距离的最大值，用$D\left(t\right)$ 表示网络的迭代次数$t$ 时的直径。由图2易知，当$t=1$ 时，直径由当前迭代次数中新添加的顶点中某两个顶点间的距离决定。且$t>1$ 时与$t=1$ 时具有相同直径。因此，该网络直径为$D\left(t\right)=3m$ 。

3.2. 聚类系数

聚类系数通过对所有顶点的聚类系数取平均值所得到，$C_i$ 为顶点$i$ 的聚类系数，$k_i$ 为顶点$i$ 的度，$L_i$ 为顶点$i$ 与其邻接点之间可能存在的边数为$C_i=\frac{2L_i}{k_i\left(k_i-1\right)}$ 。因此，对于网络$G_t$ 每次迭代都有$C_i=0$ ，该网络的聚类系数为0。

3.3. 度分布

首先，计算网络中任意选择的一个节点有$k$ 条边连接的概率：当$t=1$ 时，网络$G_t$ 中的节点度有两种情形：$m\left(t+2\right)$ 个2度点，$2m$ 个$t+3$ 度点，且接下来的每一次迭代都有此情形。因此，网络$G_t$ 节点的累加度分布为：

$p_{cum}\left(k\right)={\displaystyle \sum _{k=i}^{\infty }p\left(m+k\right)}={\displaystyle \sum _{k=i}^{\infty }\frac{N_t\left(m+k\right)}{N_t}}=\{\begin{array}{l}1,k\le 2\hfill \\ \frac{2}{t+4},2<k\le t+3\hfill \\ 0,k>t+3\hfill \end{array}$ (1)

3.4. 生成树数目

$G_t$ 的生成树数目为：

$\tau \left(G_t\right)=2^{m\left(t+1\right)}m{\left(t+2\right)}^{m-1}\left(t+4\right)$ (2)

为了方便计算，在计算环形网络的生成树数目之前，本文引入引理2.1。

引理2.1：子网络$F_t$ 的生成树数目为：

$\tau \left(F_t\right)={\left(\begin{array}{c}2\\ 1\end{array}\right)}^{t-2}\left[\left(\begin{array}{c}2\left(t-2\right)\\ 1\end{array}\right)+2\right]=2^{t+1}\left(t+2\right)$ (3)

证明：根据生成树的定义和破圈法产生生成树的原则，由$F_t$ 结构易知，破圈有两种情形：

情形1：从$\left(1,u_i\right)$ 和$\left(1,v_i\right)$ 中选择一条边破圈，在此情况下生成树的数目为：

$\tau \left(F_t\right)=2^{t+1}\left(t+1\right)$ (4)

采用数学归纳法进行证明：

当$t=0$ 时，$\tau \left(F_t\right)=4$ 。式(2)成立。假设在$t=k$ 的情况下，式(2)成立。

则当$t=k+1$ 时，网络$F_{k+1}$ 是$F_k$ 增加一个中心节点$m_i$ 且增加两条边$\left(m_i,u_i\right)$ 和$\left(m_i,v_i\right)$ 得到。因此，生成树数目满足等式$\tau \left(F_t\right)=2\tau \left(F_{t-1}\right)$ 。

所以，当$t=k+1$ 时，

$\tau \left(F_{k+1}\right)=2\tau \left(F_k\right)=2^{k+2}\left(k+2\right)$ (5)

情形2：不选择从$\left(1,u_i\right)$ 和$\left(1,v_i\right)$ 中的任何一条边进行破圈，此时，需从剩余的$t+1$ 组边(每组2条边)中选择一条破圈。则其生成树的数目为$\tau \left(F_t\right)=2^{t+1}$ 。

两种情形求和得到，网络$F_t$ 生成树数目为$\tau \left(F_t\right)=2^{t+1}\left(t+1\right)+2^{t+1}=2^{t+1}\left(t+2\right)$ ，从而引理2.1成立。

接着，我们计算$G_t$ 的生成树数目，接着，考虑$G_t$ 与$F_t$ 之间的关系，$G_t$ 是由$m$ 条连接边连接$m$ 个子网络$F_t$ 所构成，从而在计算$G_t$ 的生成树数目时，主要分为以下两个情形：

情形1：从连接$F_t$ 的$m$ 条连接边中选择一条破圈。

在此情况下，计算$G_t$ 的生成树数目可分解为计算$m$ 个子网络$F_t$ 的生成树数目，结合引理2.1易知，$G_t$ 生成树数目为：

$\tau \left(G_t\right)=2^{m\left(t+1\right)}m{\left(t+2\right)}^m$ (6)

情形2：连接$F_t$ 的$m$ 条连接边均不破开。此时，有且仅有$F_t$ 中的$t+2$ 组边(每组2条边)中的一条边破开，剩余$t-1$ 组边保持连通，共$2^{t-1}\cdot m$ 种方式。结合引理2.1得生成树数目为：

$\tau \left(G_t\right)=2^{t+2+\left(t+1\right)\left(m-1\right)}m$ (7)

将两种情形求和，网络$G_t$ 生成树数目满足式(2)。

通过生成树的数目计算出该网络的熵为：

$E_{st}\left(G_t\right)=\underset{m\to \infty }{\lim }\frac{\ln \tau \left(G_t\right)}{N_t}=\ln 2=0.693$

4. 网络${G^{\prime }}_t$ 的拓扑性质

4.1. 网络构成

在上一章节中，我们得到了网络$G_t$ 的拓扑性质。在这一章节中，我们对其收缩网络的结构进行介绍并计算其拓扑性质。用$t^{\prime }$ 来表示该网络模型的生成步数，${G^{\prime }}_t$ 表示在第$t$ 步时所生成的网络，其中，$t=0,1,2,T-1$ ，收缩网络${G^{\prime }}_t$ 的过程描述如下：(如图3所示)

(1) 选择网络中的连接边$\left(u_i,v_i\right)$ ，其中$u_i$ 和$v_i$ 为网络中的两个节点，且$u_i$ 和$v_i$ 之间存在边连接。

(2) 删除原有的边$\left(u_i,v_i\right)$ 。

(3) 将节点$u_i$ 和$v_i$ 合并成一个新的节点$t$ ，记作：$w_i=u_i\cup v_i$ 。

Figure 3. Network with edge contraction ${G^{\prime }}_t$

图3. 边收缩网络${G^{\prime }}_t$

通过计算得到${G^{\prime }}_t$ 的节点数为${N^{″}}_t=m\left(t+3\right)\left(t\ge 1\right)$ ，边数${E^{″}}_t=m\left(2t+5\right)\left(t\ge 1\right)$ 。

4.2. 直径

用$D^{\prime }\left(t\right)$ 表示网络${G^{\prime }}_t$ 的迭代次数$t$ 时的直径。由图3易知，当$t=1$ 时，直径由当前迭代次数中新添加的顶点中某两个顶点间的距离决定。且$t>1$ 时与$t=1$ 时具有相同直径。因此，该网络直径为$D^{\prime }\left(t\right)=2m$ 。

4.3. 聚类系数

因为对网络$G_t$ 进行边收缩仅是删除原有连接边$\left(u_i,v_i\right)$ 并将节点$u_i$ 和$v_i$ 合并成一个新的节点$w_i$ ，因此，聚类系数仍为0。

4.4. 度分布

首先，计算网络${G^{″}}_t$ 中任意选择的一个节点有$k$ 条边连接的概率：当$t=1$ 时，网络${G^{″}}_t$ 中节点度数有两种情形：$m\left(t+2\right)$ 个2度点，$2m$ 个$2\left(t+3\right)$ 度点，且接下来的每一次迭代都有此情形。因此，该网络的节点的累加度分布为：

$p_{cum}\left(k\right)={\displaystyle \sum _{k=i}^{\infty }p\left(m+k\right)}={\displaystyle \sum _{k=i}^{\infty }\frac{N_t\left(m+k\right)}{N_t}}=\{\begin{array}{l}1,k\le 2\hfill \\ \frac{1}{t+3},2<k\le t+3\hfill \\ 0,k>t+3\hfill \end{array}$ (8)

4.5. 生成树数目

对于变形网络${G^{\prime }}_t$ ，子网络$F_t$ 中的$t+2$ 组边(每组2条边)中的一条边破开，剩余$t-1$ 组边保持连通，共$2^{t-1}\cdot m$ 种方式。结合引理2.1网络${G^{\prime }}_t$ 生成树数目为$\tau \left({G^{\prime }}_t\right)=m\cdot 2^{t+2+\left(t+1\right)\left(m-1\right)}$ 。

通过生成树的数目计算出该网络的熵为：

$E_{st}\left(G_t\right)=\underset{m\to \infty }{\lim }\frac{\ln \tau \left(G_t\right)}{N_t}=m\cdot \ln 2$

5. 网络G_t的最小生成树探究

最小生成树是网络的生成树当中最特殊的树形网络，它不仅在通信网络、电力系统、城市规划等领域中扮演着优化网络布局降低建设成本的关键角色，并且从理论研究层面来看，在计算机科学领域中，最小生成树的求解方法也因网络而异。在处理稀疏网络时，选择Kruskal算法更合适，而Prim算法则更适合求解稠密图的最小生成树。因此，我们先对这一类环形网络的稀疏性及稠密性进行判别。

5.1. 网络G_t的稀疏性及稠密性

稀疏图是指边数$E_t$ 相对于顶点数$N_t$ 显著较少的图，在图的结构中，边的数量远小于最大边数具体来说，边数$E_t$ 远小于顶点数$N_t$ 的平方。即$E_t={\rm O}\left(v_t\right)$ 。而稠密图是指边数$E_t$ 接近或等于最大边数。边数$E_t$ 的数量级接近${\rm O}\left(v^2\right)$ ，即随着图中节点数的增加，图的边数接近二次增长。

对于网络$G_t$ ，已知节点数$N_t=m\cdot \left(t+4\right)$ ，$E_t=m\left(2t+5\right)$ 。通过对比分析，具有$N_t$ 个节点的完全图的边数为：

$\frac{N_t\left(N_t-1\right)}{2}=\frac{2m\left(t+4\right)\cdot \left(m\left(t+3\right)\right)}{2}$ (9)

当$t$ 和$m$ 增大时，完全图的边数是关于$t$ 的二次函数，而$E_t$ 关于$t$ 的一次函数，由于二次函数的增长速度比一次函数快得多，所以，式(9)成立：因此，网络$G_t$ 是稀疏网络，适用Kruskal算法探究其最小生成树。

5.2. Kruskal算法探究最小生成树的算法复杂度分析

算法复杂度分析衡量了算法在执行过程中所需资源的程度，尤其是在处理大规模数据时，选择时间复杂度较低、空间利用较高效的算法可以显著提高程序的执行效率。由于本文所研究的网络$G_t$ 由$m$ 个连接边连接$m$ 个子网络$F_t$ 所构成形成一个环形网络，且$m$ 个子网络结构相同，分别对子网络$F_t$ 以及环形网络$G_t$ 的算法复杂度进行分析。

5.2.1. Kruskal算法的时间复杂度分析

Kruskal算法的总时间复杂度主要由排序和查集操作两部分组成：其中边排序是Kruskal算法的第一部分，对于子网络$F_t$ 而言，网络中共有边数$2t+4$ 条，从而其排序算法的时间复杂度为：${\rm O}\left(2t+4\log \left(2t+4\right)\right)$ 。而第二部分查找和合并操作的时间复杂度为近乎常数时间，记作：${\rm O}\left(\alpha \left(N_t\right)\right)$ ，由于${\rm O}\left(\alpha \left(N_t\right)\right)$ 的增长极为缓慢，忽略不计。因此，该网络综合时间复杂度为${\rm O}\left(2t+4\log \left(2t+4\right)\right)$ 。

同理环形网络$G_t$ 的综合时间复杂度为${\rm O}\left(m\left(2t+5\right)\right)$ 。

5.2.2. Kruskal算法的空间复杂度分析

Kruskal算法的空间复杂度主要由存储边以及并查集操作两部分构成：对于子网络$F_t$ 而言，需要存储网络$2t+4$ 条边，且并查集结构需要存储$2t+4$ 个节点信息。因此其空间复杂度为${\rm O}\left(3t+8\right)$ 。同理，网络$G_t$ 的空间复杂度为${\rm O}\left(m\left(4t+9\right)\right)$ 。

对比两种网络的复杂度，子网络时间复杂度呈线性增长，环形网络$G_t$ 时间复杂度呈对数线性增长。并且，随着子网络数量$m$ 的增加，环形网络$G_t$ 的资源消耗显著增加。

因此，子网络$F_t$ 在时间和空间复杂度上都比环形网络$G_t$ 要低。我们先采用Kruskal算法对子网络的最小生成树进行研究。

5.3. Kruskal算法探究最小生成树算法设计

根据算法复杂度的分析，为了简化算法复杂度，我们先采用Kruskal算法对子网络的最小生成树进行研究。具体算法步骤如下：

(1) 网络的构造

首先，定义一个函数，根据输入的$t$ 值动态生成子网络$F_t$ ，其中，$t$ 表示网络的迭代次数，初始化一个空的网络$F_t$ ，用于存储节点集及边集，接着构造网络：

当$t=0$ 时，网络是一个简单的四边形结构，其节点集表示为$v_0=\left\{0,1,2,3\right\}$ ，边集表示为$E_0=\left\{\left(0,1\right),\left(1,2\right),\left(2,3\right),\left(3,0\right)\right\}$ 。

当$t\ge 1$ 时，每迭代一次，网络中都会添加一个新的节点，且新增节点与节点1和节点3相连。将新加入的节点按顺顺时针顺序编号为：$\left\{5,6,7,\cdots \right\}$ 。因此，当$t>1$ 时，节点集$V_t$ 是由节点集$V_1$ 扩展得到的，共$t+4$ 个节点，节点集为$V_t=\left\{0,1,2,\cdots ,t+4\right\}$ 。对于每个新增节点$i$ $\left(i=5,6,\cdots ,t+4\right)$ 都与节点1和节点3连接。其边集为$E_1\cup \left\{\left(i,1\right),\left(i,3\right)|i=5,6,\cdots ,t+4\right\}$ 。

(2) 边集的排序

在初始网络$F_0$ 中，将四条边分别赋任意赋权为：

$w\left(0,1\right)=a,w\left(1,2\right)=b,w\left(2,3\right)=c,w\left(3,0\right)=d$

当$t>1$ 时，每增加一个节点，新的节点与节点1节点3连接，边权赋值进行动态变化，其权重为$\left\{w\left(i,1\right)=e_i,w\left(i,3\right)=f_t\right\}$ 。

在对边进行任意赋权的基础上，将所有边的权值按从小到大的顺序排列，特别地，每条边的赋值由用户自行在表单输入界面进行输入，然后算法通过排序保证每次处理的是当前图中权重最小的边。

(3) 使用并查集(Union-Find)管理连通性

在使用并查集前，对网络$F_t$ 进行初始化，为每个节点创建一个独立的连通分量。本文所采用数组来实现并查集，数组的索引表示节点编号，数组的值表示该节点的父节点。将每个节点的父节初始化为自身。同时可以引入一个rank数组来记录每个连通分量的树的高度。最终，使用find操作进行用路径压缩以提高效率。确定某个节点所属的连通分量的根节点。

(4) 使用Union操作合作连通分量

在处理排序后的边集时，对于每条边，需要判断其是否属于同一个连通分量。如果不属于同一个连通分量，就需要将它们所在的连通分量合并。在合并两个节点的连通分量时，通过按秩合并技术合并两个节点所在的集合。每次将边加入生成树时，更新其两个端点所在的连通分量。确保它们属于同一连通分量，避免树的高度过大，提升操作效率。

(5) 判断程序结束条件

当网络中所有边都被处理完，或是网络中所有节点都属于同一个连通分量时，最小生成树构建完成，算法结束。

(6) 增值循环

每处理完一条边，对循环计数器进行更新，并继续处理下一条边。若图中已连接所有节点，则算法结束并输出最终所构建的生成树。

通过上述操作我们已经得到了子网络$F_t$ 的最小生成树结构，本文所研究的网络$G_t$ 是由$m$ 个连接边连接$m$ 个子网络$F_t$ 所形成的环形网络，每一条连接边任意赋权为：$\left\{W_1,W_2,\cdots ,W_m\right\}$ ，按照权值大小升序进行排序，去掉权重最大的连接边，其余$m-1$ 条连接边按照网络$G_t$ 的连接方式连接子网络$G_t$ 的最小生成树。最终，能够得到网络$G_t$ 的最小生成树的结构以及其权重之和。

5.4. 最小生成树的应用

最小生成树是一种特殊的树形网络结构，国内外学者纷纷将复杂网络应用于研究金融系统的复杂性。Haldane、May等人通过对电信网络及传染病传播网络的类比提出了采用冲击银行资产负债表的方式来探究银行系统的脆弱性。自此以后，最小生成树的推广与应用十分宽泛。广泛应用于社交网络、通信网络、交通网络、物流网络等网络中。

基于本文所构建的环形网络模型$G_t$ 进行案例分析，模拟一个真实的社交网络，人与人之间相互的关系为边线连接。通过最小生成树算法探究该社交网络的最小生成树结构可以帮助评估社交网络的稳定性，我们假设在网络模型$G_t$ 中，迭代次数$t$ 值为3，连接边数目$m$ 为3。社交网络结构如图4所示。

Figure 4. Social network $G_t$ simulation with small vertices

图4. 小顶点下的社交网络$G_t$ 模拟

在该网络模型中，每个节点代表就是社交网络中的一个用户，每个子网络$F_t$ 代表着一个社交团体。在每一个子网络$F_t$ 的内部权重相同，根据其社交影响力的不同，子网络$F_t$ 当中最外围用户之间边的权重分别模拟为$\left\{10,9,8,7,\cdots \right\}$ ，基于上算法步骤生成最小生成树。子网络$F_t$ 的最小生成树构建完成如图5所示。

在得到子网络的最小生成树结构后，我们将每个子网络的最大度节点1和3模拟为具有广泛社交联系和强大影响力的用户，这些用户具备较强的传播能力，传播成本也较低。所以，我们将连接这些节点的边权值模拟为最小值。其权重分别为：

$w\left(1,1\right)=3,w\left(3,1\right)=2,w\left(3,3\right)=1$

我们去掉连接边的最大权重边，按照$G_t$ 的连接方式将各个子网络的最小生成树连接起来。最终得到社交网络$G_t$ 的最小生成树结构如图6所示。

Figure 5. Minimum spanning tree structure of a subnetwork $F_t$

图5. 子网络$F_t$ 的最小生成树结构

Figure 6. Minimum spanning tree structure of the social network $G_t$

图6. 社交网络$G_t$ 的最小生成树结构

6. 结语

首先介绍了一类环形网络的演化过程与相关概念，通过网络中拓扑性质的定义计算了网络的拓扑特性以及网络中生成树的枚举问题。给出了这类网络生成树数目的计算方法，得出了生成树数目的确解。然后，在此基础上，进一步推导了这类网络连接边进行边收缩后其变形网络的拓扑性质。最后，本文分析了在任意边赋权下该类环形网络的最小生成树问题，提出了一种算法，能够在任意条件下确定最小生成树的结构。针对小规模网络，使用Python进行了实例分析，验证了该算法的实用性与有效性，为实际应用提供了理论支持与实践依据。

基金项目

青海民族大学研究生创新项目《一些网络的生成树计数研究》。项目编号：07M2024017。