双权重三角网络上的随机游走研究

Research on Random Walks on Dual-Weighted Triangular Networks

摘要: 由于确定性加权网络被广泛应用于模拟现实世界的复杂系统。本文主要研究双权重三角网络上的平均陷阱时间。我们定义内生长，即网络中已存在的内部新增节点的过程；外生长，即网络的现有结构之外添加新节点。在内生长和外生长的基础上，引入内生长权重因子q和外生长权重因子r。根据自相似网络的良好性质，通过迭代算法获得平均陷阱时间的解析式，结果显示服从指数为$\frac{ln\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}}{ln5}$ 的幂律函数，该指数与内生长权重因子q和外生长权重因子r有关，且权重因子r、q越小，该陷阱捕获过程越高效。

Abstract: Deterministic weighted networks are widely used to simulate complex systems in the real world. This paper focuses on the average trapping time on dual-weighted triangular networks. We define internal growth as the process of adding new nodes within the existing structure of the network, and external growth as the process of adding new nodes outside the existing structure of the network. Based on internal and external growth, we introduce the internal growth weight factor q and the external growth weight factor r. Leveraging the excellent properties of self-similar networks, we derive the analytical formula of the average trapping time through an iterative algorithm. The results show that it follows a power-law function with an exponent of $\frac{ln\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}}{ln5}$ , which is related to the internal growth weight factor q and the external growth weight factor r. Moreover, the smaller the weight factors r and q, the more efficient the trapping process.

1. 绪论

随着互联网、物联网、交通网等各类网络在生活中的不断发展，学者们逐渐认识到现实生活与复杂网络之间存在着密不可分的联系。通过分析网络的拓扑结构和性质，能够将现实生活中的大型网络转化为度量空间里的复杂网络。随机游走作为一种基础的动力学过程，其作用在于通过研究复杂网络中节点间的随机游走关系，来模拟现实网络中元素之间的连接情况，进而实现对节点连接性、信息传播以及网络自身性质的研究。不仅如此，学者们还在无权重网络的基础上进行拓展，构建出了加权网络。他们通过为连边设定不同的权重，也就是引入权重异质性，使得节点在选择路径时存在不同的概率，从而构建出更贴近真实世界的复杂网络。

为了贯彻落实我国加快建设科技强国、实现高水平科技自立自强的重要战略部署，本项目计划对自相似网络上随机游走的扩散效率展开研究。在过去的几十年里，复杂网络在科学界受到了学者们的广泛关注。在社交网络中，随机游走可以对信息的传播方式进行模拟，帮助我们理解信息在网络中的扩散机制；在生物网络中，它能够用于研究分子在细胞内的扩散过程；此外，随机游走在搜索引擎算法中也发挥着重要作用，例如谷歌的PageRank算法[1]就是基于随机游走原理开发的。对复杂网络的研究，有助于我们理解各类系统[2] (如社交网络、生物网络、交通网络等)的行为模式和特征，进而揭示系统内部的规律和机制。通过研究复杂网络，还能优化各种大型系统的设计与管理，提高其效率、韧性和可持续性，比如改善交通流量、优化电力网络分布、增强社交网络的连接性等。同时，复杂网络研究为解决实际问题提供了理论基础和方法论支持，像灾害应对、疾病控制、社会动态预测等领域都能从中受益。而且，深入研究复杂网络，有可能发现新的规律和现象，为各个领域的创新发展提供新的思路和方法。

随着复杂网络的兴起，学者们发现通过模拟各种网络，复杂网络能够反映出真实网络中存在的内部连接，如金融网络、社交网络、病毒网络等。学者们从复杂网络的拓扑结构入手，通过研究和分析其小世界性、无标度性质来模拟真实网络。例如，Watts和Strogtz [3]在1998年受到生物神经网络和电网的启发，构建了具有小世界动力系统的模型，该模型刻画了真实网络所具有的大聚簇和短平均路径距离的性质；Barabasi和Albert [4]在1999年通过扩展网络的顶点，发现网络中已有的节点越受欢迎(即度数越高)，就越有可能与新节点建立连接，由此建立了无标度模型；2005年，Song等人[5]通过分析大量现实网络，得出它们存在自重复模式的结论，并定义了有限的自相似指数。通过对这些拓扑属性的分析研究，我们基于现实网络构建的网络模型能够更好地模拟并优化真实网络的结构。

众多学者对分形网络展开了大量研究，在网络科学领域，研究人员深入探讨了多种复杂网络结构中粒子的随机游走行为，这些网络结构包括但不限于自相似网络。自相似网络具有在不同尺度上展现出相似模式的自相似性质。在这些网络上，粒子的游走可以通过多种策略进行模拟，如标准权重游走[6] [7]、非标准游走[8]、混合游走[9]、延迟随机游走[10] [11]、大象游走[12]等。基于这些游走方式，学者们还考虑了一种由Montrol等人提出的陷阱问题，该问题描述的是物理粒子在网络上随机游走时被捕获或吸收的效率，它在物理、化学以及生物系统中都有广泛应用。学者们也对多种不同的网络模型进行了研究，如Sierpinski垫片、无标度网络[13]-[15]、Koch曲线、加权分层网络等。另外，相关学者还研究了加权无标度三角网络[16]，并进一步将其扩展到m-三角网络，从而定义了特殊的三角网络。他们的研究成果为深入理解加权网络中随机游走行为提供了帮助，这对于研究网络中的信息传播、疾病控制和搜索算法等领域具有重要意义。不过，复杂网络是否具有普遍的动力学机制，以及如何将复杂网络的研究成果应用到实际工程和现实网络中，这些都是复杂网络发展过程中面临的挑战性难题。

本文主要研究了双权重三角网络的平均陷阱时间，其创新点在于定义了内生长与外生长，并为它们赋予了不同的权重。该模型在病毒传播领域具有重要意义，尤其是在理解病毒如何在人际网络中传播方面。在多关系网络上的流行病传播动力学研究中发现，多关系的存在会显著降低网络中的爆发阈值，使得疾病更容易流行且难以控制；而在单点接触模式下，增加强关系的权重可以显著提升爆发阈值，降低感染密度。这些发现有助于我们理解多关系网络上的病毒传播过程，并为多关系网络研究提供了新的视角。

第一章绪论主要阐述了复杂网络的研究背景、目的和意义，概述了目前国内外的研究现状，并在此基础上说明了本文研究双权重三角网络的意义。

第二章介绍了双权重三角网络，在过往研究的基础上定义了外生长与内生长，并基于此模型研究其平均陷阱时间。首先，当陷阱吸引点位于依权游走中度最高的节点时，利用网络结构的自相似性，找到上下代之间的迭代关系，最终得到了平均陷阱时间的精确解析式。结果显示，其表达式关于网络规模遵

从指数为$\frac{\ln \frac{2+4\left(q+r\right)}{2+\left(q+r\right)}}{\ln 5}$ 的幂律函数。将平均陷阱时间的解析解和数值解进行比较后发现，两者高度一

致，这一结果进一步验证了所得到的平均陷阱时间解析式的正确性。

2. 双权重三角网络的平均陷阱时间

2.1. 内生长与外生长

(1) 内生长：网络中已经存在的内部增加新节点的过程。这种生长方式是在现有网络结构的基础上进行的，新加入的节点与原有的网络对应节点相连，形成一个新的、内部的连接。

(2) 外生长：网络的现有结构之外添加新节点，并与现有节点建立连接的过程。这种生长方式扩展了网络的边界，新节点通常与一个或多个现有节点相连，但不是网络内部的节点。

例如，在病毒的人际传播网络中，其扩散呈现典型的“社区内高频接触(内生长) + 跨社区低频接触(外生长)”双路径模式。家庭、工作场所等封闭环境内的密切接触可被内生长权重因子q表示，而跨社区的随机偶遇则由外生长权重因子r表征，两者共同决定了超级传播者节点的形成与扩散速度。模型中的陷阱时间${\langle T\rangle }_t$ 对应病毒从初始感染者到被“检测隔离”所需时间，当q与r越小，病毒在本地或远程传播的“边权重”越弱，从任意节点游走到陷阱节点的路径更短、更集中，从而病毒捕获效率越高。

本文所定义的内生长与外生长模型，在多种基础网络上具有一定的通用性，可以进行拓展应用。在随机网络中，可以进一步探索生长过程的随机性对网络整体以及动力学等方面的影响；在复杂网络中，内生长与外生长模型可以用于讨论生长机制与网络固有特征之间的相互作用。

2.2. 双权重三角网络

受二元网络及加权无标度三角网络的启发，我们引入了以内生长权因子q，外生长权因子r的双权重三角网络，其中r (0 < r ≤ 1)，q (0 < q ≤ 1)是正实数。由该网络是通过迭代的方式产生的，因此其结构具有良好的自相似性。设$G_t$ 表示经过t次迭代后的双权重三角网络，下面我们建立该种网络的模型：

(i) 首先(对t = 0)，$G_0$ 是一个由三个节点三条边组成的三角形，将三个节点记为A，B，C，三条边赋予单位权重；

(ii) 当t ≥ 1时，$G_{t-1}$ 中的每条边都产生2个新节点，分别遵循内生长与外生长的迭代规律，且每一个新节点都与原来边的两个端点相连。由此得到经过t次迭代后的双权重三角网络$G_t$ 。因此，每个新节点关联的边数，即度为2，与此同时内生长的边权重为权因子q (0 < q ≤ 1)，外生长的边权重为权因子r (0 < r ≤ 1)。图1展示了双权重三角网络中，当每条老边新产生两个节点时，经过t次迭代后的网络$G_t$ 从t = 0到t = 2共三代的迭代过程。

Figure 1. Iterative process of the first three generations of network G_t from t = 0 to t = 2 when each edge generates two new nodes, nodes in red are generated at generation t = 1; nodes in yellow are generated at generation t = 2. Each pink edge has a weight of r, each light green edge has a weight of q, each red edge has a weight of r², each dark green edge has a weight of q², and each yellow edge has a weight of qr

图1. 当每条边新产生两个节点时，网络G_t从t = 0到t = 2的前三代的迭代过程，红色节点在t = 1代时产生；黄色节点在t = 2代产生；且每条粉边权重为r，每条浅绿边权重为q，每条红边权重为r²，深绿边权重为q²，每条黄边权重为qr

以下文献主要来自[17]。从迭代过程来看，我们可以得出该网络的一些基本量，这些基本量对于本章探求该种网络上的平均陷阱时间不可或缺。若记$E_t$ 、$N_t$ 分别是经过t次迭代后的网络$G_t$ 的总边数和总节点数，根据网络的构造过程，第$t-1$ 代的每条边在第t代都产生2个新节点、4条新边。只不过我们是双权重，由文献即得：

$E_t=3\cdot 5^t,N_t=\frac{3}{2}\cdot 5^t+\frac{3}{2}$ (1)

根据这些基本量可以得知，各节点的度在每一代都有所不同。根据节点度的定义，若令$k_i\left(t\right)$ 表示网络$G_t$ ($0\le t_n\le t$ )中第$t_n$ 步节点i的度，这里$\left\{t_n\right\}$ 是$\left\{t\right\}$ 的一个子序列，根据网络上下代之间的关系及网络结构本身的自相似性，我们可以得出$k_i\left(t\right)=3k_i\left(t-1\right)$ 。如果节点i在第$\left\{t_n\right\}$ 步产生，由于每个新节点的度为2，那么$k_i\left(t_n\right)=2$ 。因此节点i在第t次迭代的度$k_i\left(t\right)$ ，有：

$k_i\left(t\right)=2\cdot 3^{t-t_n}$ (2)

分步数是为了区分上下代，第一步边的权重为r、q，第二步边的权重为r²、q²、rq，这样数对应步数的边的数量相当于数r、q与r²、q²、rq在这一代的个数。由节点强度的定义，即连接到节点的边的权重的总和：

$s_i\left(t\right)=\left(1+q+r\right)s_i\left(t-1\right)$ (3)

例如，对于$G_t$ 中的节点A来说，其强度$s_A\left(t\right)=2{\left(1+q+r\right)}^t$ 。

为了更好地理解本章研究的网络模型，除了研究节点的度，我们也关心该网络模型的度分布。由等式(2)可知，网络的度谱是离散的，若令$n_v\left(t\right)$ 表示第t步节点的个数，那么我们可以得到如下的度分布：

$P\left(k\right)=\{\begin{array}{ll}\frac{n_v\left(0\right)}{N_t}=\frac{2}{5^t+1},\hfill & t_n=0\hfill \\ \frac{n_v\left(t_n\right)}{N_t}=\frac{5^{t_{n-1}}\cdot 4}{5^t+1},\hfill & t_n\ge 1\hfill \\ 0,\hfill & 其他\hfill \end{array}$ (4)

因此其累积度分布可表示为：

${\displaystyle \sum }_{t=0}^{t_n}{P}_{cum}\left(k\right)={\displaystyle \sum }_{\mu \le t_n}\frac{n_v\left(\mu \right)}{N_t}=\frac{5^{t_n}+1}{5^t+1}$ (5)

从等式(2)可知$t_n=t-\frac{\ln \frac{k}{2}}{\ln \left(m+1\right)}$ ，将$t_n$ 代入累积度分布等式(5)后，可获得其精确表达式为：

$P_{cum}\left(k\right)=\frac{5^t{\left(\frac{k}{2}\right)}^{-\frac{\ln 5}{\ln 3}}+1}{5^t+1}$ (6)

且当网络逐次迭代即t较大时：

$P_{cum}\left(k\right)~{\left(\frac{k}{2}\right)}^{-\frac{\ln 5}{\ln 3}}$ (7)

至此，我们发现该网络的度分布是无标度的且指数为${\gamma }_k=1+\frac{\ln 5}{\ln 3}$ 。

2.3. 计算m = 2加权三角无标度网络的平均陷阱时间

这一节我们的主要目标是计算出双权重三角网络的平均陷阱时间的精确表达式。考虑该种网络上的

依权重游走，我们可知行走者从当前节点i选择到其最近相邻节点j的转移概率为$P_{ij}=\frac{w_{ij}}{s_i}$ 在该网络模型

中，定义$T_i^t$ 表示第t代网络$G_t$ 上的平均首次通过时间(MFPT)，它是行走者从节点i到达中心陷阱节点固定在度最高节点的期望时间。不失一般性，我们可以将陷阱节点固定在第t代网络$G_t$ 中的节点A。平均首次通过时间$T_i^t$ 满足：

$T_i^t={\displaystyle \sum _{j=2}^{N_t}{p}_{ij}{T}_j^t}+1$ (8)

且其对应的矩阵可以表示为：

$T=PT+e$ (9)

这里$T=\left(T_2^t,T_3^t,\cdots ,T_{N_t}^t\right)$ 是一个$N_{t-1}$ 维的列向量，e是所有元素为1的$N_{t-1}$ 维的列向量，$P=\left(p_{ij}\right)$ 是阶数为$N_{t-1}$ 的方阵。因此：

$T={\left(I-P\right)}^{-1}e$ (10)

这里I是阶数为$N_{t-1}$ 的单位矩阵。

对于本节要考虑的平均陷阱时间(ATT)，它是由$G_t$ 上除了陷阱节点以外的所有初始节点的平均首次通过时间$T_i^t$ 的期望来定义，记作${\langle T\rangle }_t$ ，因此可以写为：

${\langle T\rangle }_t=\frac{1}{N_t-1}{\displaystyle \sum _{i=2}^{N_t}{T}_i^t}=\frac{1}{N_t-1}{\displaystyle \sum _{i=2}^{N_t}{\displaystyle \sum _{j=2}^{N_t}{\tau }_{ij}}}$ (11)

这里${\tau }_{ij}$ 是矩阵${\left(I-P\right)}^{-1}$ 的第i行第j列元素。由上述表达式可以看出，若想求出平均陷阱时间，即需求出矩阵${\left(I-P\right)}^{-1}$ 中所有元素的和。但对于阶数较大的网络，这样的计算量是相当大的。为此，若将第t代所有节点的平均首次通过时间之和记为$T_{t,total}^t$ ，这里我们另外给出双权重三角网络上平均陷阱时间的精确计算，即令$T_{t,total}^t={\displaystyle {\sum }_{i=2}^{N_t}{T}_i^t}$ ，那么根据定义可得：

${\langle T\rangle }_t=\frac{1}{N_t-1}{T}_{t,total}^t$ (12)

因此，我们只需要计算出$T_{t,total}^t$ ，即可获得平均陷阱时间的精确表达式。

为了求出第t代所有节点的平均首次通过时间之和$T_{t,total}^t$ ，本文我们通过将第t代网络$G_t$ 划分层次的方法来计算。在建立该网络的过程中，我们发现第$t-1$ 代网络$G_{t-1}$ 的任意点i经过一次迭代到第t代网络$G_t$ 后，其强度会由原来的$s_i\left(t-1\right)$ 增至$\left(1+2r\right)s_i\left(t-1\right)$ ，且节点i的度以2倍增长，即$k_i\left(t\right)=3k_i\left(t-1\right)$ 。这$3k_i\left(t-1\right)$ 个节点i的邻点可分为两类：

(i) 第$t-1$ 代网络$G_{t-1}$ 的每个节点原来有$k_i\left(t-1\right)$ 个邻点，称为老点；

(ii) 在第t代网络$G_t$ 上又新产生$2k_i\left(t-1\right)$ 个邻点，称为新点。

记X代表从节点i到其任一$k_i\left(t-1\right)$ 个老邻点的平均首次通过时间，它包含两种，其一是从节点i直接到其任一$k_i\left(t-1\right)$ 个老邻点，概率是$\frac{1}{1+q+r}$ ，总时间为$1\times \frac{1}{1+q+r}$ ，其二是由节点i到$k_i\left(t\right)$ 个新邻点后再由新邻点到其任一$k_i\left(t-1\right)$ 个老邻点；记Y为从外生长节点i的任意$k_i\left(t-1\right)$ 个新邻点到其$k_i\left(t-1\right)$ 个老邻点之一的平均首次通过时间，则X经过外生长到老邻点概率是$\frac{r}{1+q+r}$ ，所需时间为$\frac{r}{1+q+r}\left(1+Y\right)$ ；记Z为从内生长节点i的任意$k_i\left(t-1\right)$ 个新邻点到其$k_i\left(t-1\right)$ 个老邻点之一的平均首次通过时间，则X经过内生长到老邻点概率是$\frac{q}{1+q+r}$ ，所需时间为$\frac{q}{1+q+r}\left(1+Z\right)$ 。

考虑外生长的新点，从新点到老邻点有两种路径，其一是直接到老邻点，概率是$\frac{1}{2}$ ，所需时间为$1\times \frac{1}{2}$ ，另一种是经过i，概率是$\frac{1}{2}$ ，所需时间为$\frac{1}{2}\left(1+X\right)$ ，内生长同理。这里的X、Y、Z是网络连续几代间与平均首次通过时间相关的无量纲数，通过网络的建构过程，我们可以建立如下方程：

$\{\begin{array}{l}X=\frac{1}{1+q+r}+\frac{r}{1+q+r}\left(1+Y\right)+\frac{q}{1+q+r}\left(1+Z\right)\\ Y=\frac{1}{2}\left(1+X\right)+\frac{1}{2}\\ Z=\frac{1}{2}\left(1+X\right)+\frac{1}{2}\end{array}$ (13)

从等式(13)中可以解得$X=\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}$ 那么任一节点i的陷阱时间的增长因子即为$X=\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}$ 因此我们可以得到从第$t-1$ 代加权网络$G_{t=1}$ 到t代加权网络$G_t$ 平均首次通过时间的迭代过程为：

$T_i^t=\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}{T}_i^{t-1}$ (14)

有了上下代间平均首次通过时间的迭代关系，下面我们在此基础上计算$T_{t,total}^t$ 的值。定义${\Omega }_t$ 为$G_t$ 中所有节点的集合、${\overline{\Omega }}_n$ 为第n (n ≤ t)步新产生的节点的集合，那么${\Omega }_n={\Omega }_{n-1}\cup {\overline{\Omega }}_n$ 。将$T_{n,total}^t$ 定义为第n (n ≤ t)代所有节点平均首次通过时间之和、$T_{n,total}^t$ 定义为第n (n ≤ t)代所有新产生节点的平均首次通过时间之和，那么：

$T_{n,total}^t={\displaystyle \sum _{i\in {\Omega }_n}{T}_i\left(t\right)}$ (15)

${\overline{T}}_{n,total}^t={\displaystyle \sum _{i\in {\overline{\Omega }}_n}{T}_i\left(t\right)}$ (16)

因此，

$T_{t,total}^t=T_{t-1,total}^t+{\overline{T}}_{t,total}^t$ (17)

由网络本身具有的自相似性，我们可以通过上下代的递推关系计算出第t代所有新节点平均首次通过时间之和$T_{t,total}^t$ 。我们首先考虑t = 1的初始情况，将其新产生的节点从1到6进行标记(3个内生长，3个外生长)：

(i) 连接节点A和节点B的边新产生的节点标记为1到2，若初始节点i从其中选出，则$T_i^1=\frac{1}{2}\left(1+T_A^1\right)+\frac{1}{2}\left(1+T_B^1\right)$ ；

(ii) 连接节点B和节点C的边新产生的节点从3到4进行标记，若初始节点j从其中选出，则$T_j^1=\frac{1}{2}\left(1+T_B^1\right)+\frac{1}{2}\left(1+T_C^1\right)$ ；

(iii) 连接节点C和节点A的边新产生的节点从5到6进行标记，若初始节点k从其中选出，则$T_k^1=\frac{1}{2}\left(1+T_A^1\right)+\frac{1}{2}\left(1+T_C^1\right)$ 。由于每一条边经过一次迭代后均新产生m个节点，因此第一代所有新节点的平均首次通过时间和可表示为：

${\overline{T}}_{1,total}^1={\displaystyle \sum }_{i\in {}_{\overline{\text{Ω}}}}=T_i^1+T_j^1+T_k^1=6+2\left(T_A^1+T_B^1+T_C^1\right)=6+2{\overline{T}}_{0,total}^1$ (18)

值得注意的是，根据${\Omega }_t$ 的定义：

${\Omega }_t={\overline{\Omega }}_t\cup {\overline{\Omega }}_{t-1}\cup \cdots \cup {\overline{\Omega }}_1\cup {\overline{\Omega }}_0$ (19)

由于第n代的每条边均产生$2\cdot 5^{n-1}$ 个新节点，那么$\left|{\overline{\Omega }}_t\right|=6\cdot 5^{t-1}$ 。由于每个新产生的节点只有$\frac{1}{2}$ 的概率回到原来的点，因此第t代所有新节点的平均首次通过时间和为：

$\begin{array}{c}{\overline{T}}_{t,total}^t=\left|{\overline{\Omega }}_t\right|\cdot \left(\frac{1}{2}+\frac{1}{2}\left(1+T_i\left(t\right)\right)\right)\\ =\left|{\overline{\Omega }}_t\right|+\frac{1}{2}\left|{\overline{\Omega }}_t\right|T_i\left(t\right)\\ =\left|{\overline{\Omega }}_t\right|+\frac{1}{2}\times 2{\displaystyle \sum _{i\in {\Omega }_{t-1}}{k}_i\left(t-1\right)T_i\left(t\right)}\\ =\left|{\overline{\Omega }}_t\right|+{\displaystyle \sum _{i\in {\Omega }_{t-1}}{k}_i\left(t-1\right)T_i\left(t\right)}\end{array}$ (20)

将分成同一代的看成一类，若用j来表示不同的代数，由表示上下代节点i的度的关系等式(2)可得：

$\begin{array}{c}{\displaystyle \sum _{i\in {\Omega }_{t-1}}\left[k_i\left(t-1\right)T_i\left(t\right)\right]}=\left[{\displaystyle \sum _{j=1}^t{\displaystyle \sum _{i\in {\Omega }_{t-j}}{k}_i\left(t-1\right)T_i\left(t\right)}}\right]\\ =\left[{\displaystyle \sum _{j=1}^{t}2\cdot 3^{j-1{\overline{T}}_{t-j,total}^t}}\right]\\ =2{\displaystyle \sum _{j=1}^t{3}^{j-1{\overline{T}}_{t-j,total}^t}}\end{array}$ (21)

因此我们通过计算得出所有第t代新产生节点的平均首次通过时间之和及所有第$t-1$ 代新产生节点的平均首次通过时间之和：

${\overline{T}}_{t,total}^t=6\cdot 5^{t-1}+2\left[{\overline{T}}_{t-1,total}^t+3{\overline{T}}_{t-2,total}^t+\cdots +3^{t-1{\overline{T}}_{0,total}^t}\right]$ (22)

且

${\overline{T}}_{t+1,total}^{t+1}=6\cdot 5^t+2\left[{\overline{T}}_{t,total}^{t+1}+3{\overline{T}}_{t-1,total}^{t+1}+\cdots +3^{t{\overline{T}}_{0,total}^{t+1}}\right]$ (23)

将等式(23)减去等式(22)，由上下代间平均首次通过时间的等式(14)可得上下代间所有新产生节点的平均首次通过时间之和的迭代关系：

${\overline{T}}_{t+1,total}^{t+1}=\frac{10+20\left(q+r\right)}{2+q+r}{\overline{T}}_{t,total}^t+6\cdot 5^{t-1}\frac{4-7\left(q+r\right)}{2+\left(q+r\right)}$ (24)

记$M=\frac{10+20\left(q+r\right)}{2+q+r}$ ，$N=6\cdot 5^{t-1}\frac{4-7\left(q+r\right)}{2+\left(q+r\right)}$ ，则${\overline{T}}_{t+1,total}^{t+1}=M{\overline{T}}_{t,total}^t+N$ ，显然有

${\overline{T}}_{t+1,total}^{t+1}+\frac{N}{M-1}=M\left({\overline{T}}_{1,total}^1+\frac{N}{M-1}\right)$ 。

所以$\left\{{\overline{T}}_{t,total}^t+\frac{N}{M-1}\right\}$ 是等比数列，因此

${\overline{T}}_{t,total}^t=\left({\overline{T}}_{1,total}^1+\frac{N}{M-1}\right)M^{t-1}-\frac{N}{M-1}$

考虑到初始值为$T_{0,total}^0=4$ ，由等式(20)得：

${\overline{T}}_{1,total}^1=6+{\overline{T}}_0^1=6+2\cdot \frac{2+4\left(q+r\right)}{2+\left(q+r\right)}{\overline{T}}_0^0=\frac{28+38\left(q+r\right)}{2+\left(q+r\right)}$ (25)

${\overline{T}}_{t,total}^t=C\cdot {\left[\frac{10+20\left(q+r\right)}{2+\left(q+r\right)}\right]}^{t-1}-\frac{8-14\left(q+r\right)}{5\left(q+r\right)\cdot 5^{t-1}}$ (26)

这里$C=\frac{176{\left(q+r\right)}^2+120\left(q+r\right)+16}{5{\left(q+r\right)}^2+10\left(q+r\right)}$ 。

既然第t代所有节点的平均首次通过时间之和可由第$t-1$ 代所有节点的平均首次通过时间之和与第t代新产生节点的平均首次通过时间之和来表达。现在我们已经求出第t代新产生节点的平均首次通过时间之和，那么由等式(17)和等式(26)可得第t代所有节点的平均首次通过时间之和为：

$\begin{array}{c}{T}_{t,total}^t=T_{t-1,total}^t+{\overline{T}}_{t,total}^t\\ =C\cdot \frac{5}{4}{\left\{\frac{5\cdot \left[5\cdot \left(2+4\left(q+r\right)\right)\right]}{2+\left(q+r\right)}\right\}}^{t-1}\\ +\left\{4-C\cdot \frac{2+\left(q+r\right)}{4\left[2+4\left(q+r\right)\right]}-\frac{\left[2+\left(q+r\right)\right]\left[7\left(q+r\right)-4\right]\cdot 2}{5\cdot \left[8+\left(q+r\right)\right]\left(q+r\right)}\right\}\cdot {\left[\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}\right]}^t\\ +\frac{2\cdot \left[7\left(q+r\right)-4\right]\left[2+\left(q+r\right)\right]}{\left(q+r\right)\left[8+\left(q+r\right)\right]}\cdot 5^{t-1}\end{array}$ (27)

因此，由$T_{t,total}^t$ 关于平均陷阱时间的表达式等式(12)和等式(27)，我们可以计算出该网络平均陷阱时间${\langle T\rangle }_t$ 的精确表达式：

$\begin{array}{c}{\langle T\rangle }_t=\frac{1}{N_t-1}{T}_{t,total}^t\\ =\frac{C\cdot \frac{5}{2}{\left(\frac{5\cdot \left[2+4\left(q+r\right)\right]}{2+\left(q+r\right)}\right)}^{t-1}}{3\cdot 5^t+3}\\ +\frac{2\cdot \left\{4-C\cdot \frac{2+\left(q+r\right)}{4\left[2+4\left(q+r\right)\right]}-\frac{\left[2+\left(q+r\right)\right]\left[7\left(q+r\right)-4\right]\cdot 2}{5\cdot \left[8+\left(q+r\right)\right]\left(q+r\right)}\right\}\cdot {\left[\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}\right]}^t}{3\cdot 5^t+3}\\ +2\left\{\frac{\left[7\left(q+r\right)-4\right]\left[2+\left(q+r\right)\right]\cdot 2}{\left(q+r\right)\left[8+\left(q+r\right)\right]}\cdot 5^{t-1}\right\}\end{array}$ (28)

这里$C=\frac{176{\left(q+r\right)}^2+120\left(q+r\right)+16}{5{\left(q+r\right)}^2+10\left(q+r\right)}$ 。

为了考量m的值对平均陷阱时间的影响，由该网络的总节点数为$N_t=\frac{3}{2}\cdot 5^t+\frac{3}{2}$ ，因此平均陷阱时间${\langle T\rangle }_t$ 的表达式随网络的阶数遵从：

${\langle T\rangle }_t~{\left(\frac{2+4\left(q+r\right)}{2+\left(q+r\right)}\right)}^{t+1}={\left(N_t\right)}^{\frac{\ln \frac{2+4\left(q+r\right)}{2+\left(q+r\right)}}{\ln 5}}$ (29)

由0 < r ≤ 1，0 < q ≤ 1且m = 2可知$\frac{\ln \frac{2+4\left(q+r\right)}{2+\left(q+r\right)}}{\ln 5}<1$ 。这表明平均陷阱时间与网络阶数呈次线性增长模式，且r、q越小，该陷阱捕获过程越高效。

为了验证结果的准确程度，我们可以利用以上所得的表达式对该种随机游走模式进行模拟仿真。主要分为两部分，一方面在于外生长权重因子r，另一方面涉及到内生长权重因子q。首先考虑外生长因子r对捕获效率即平均陷阱时间的影响，固定q = 0.75，变化r，对于不同的r，平均陷阱时间${\langle T\rangle }_t$ 仍然是关于t的函数，r越大，所需的平均陷阱时间越长。作为代表数值解和解析解的空符号对于不同的r也仍可表现出高度的一致性。通过图2和图3可知，其一对于不同的参数r和q，平均陷阱时间的解析解和数值解基本保持高度一致；其二，考虑的两种参数确实会对平均陷阱时间产生一定影响；其三，该研究结果对其他确定性增长的加权网络上的随机游走具有一定的启示，当q取q = r为文献中单权重结果。

Figure 2. When $q=0.75$ , ${\langle T\rangle }_t$ is a function of t for different values of r, open symbols represent data from numerical solutions and analytical solutions

图2. 当$q=0.75$ 时，对于不同的r，${\langle T\rangle }_t$ 是t的函数，空符号是来自数值解和解析解数据

Figure 3. When $r=0.5$ , ${\langle T\rangle }_t$ is a function of t for different values of q, open symbols represent data from numerical solutions and analytical solutions

图3. 当$r=0.5$ 时，对于不同的q，${\langle T\rangle }_t$ 是t的函数，空符号是来自数值解和解析解数据

NOTES

^*通讯作者。