联合三分Sierpinski垫片上的平均捕获时间

张希涵，吴 波

(南京财经大学 应用数学学院，江苏 南京 210023)

0 引言

复杂网络理论由于其在自然界和社会问题研究中的广泛运用，近年来越来越受到人们的关注.在复杂网络的研究中，解释网络的拓扑结构及其动态过程之间的关系是一个重要内容.陷阱问题是一个特殊的随机游走问题，它描述了一个非捕获节点到达一个指定陷阱点所需要的时间，描述了网络的全局特征.近年来，国内外相关学者研究了(2,2)—花网络[1]、加权三角网络[2]、三分Sierpinski网络[3]、左半三级Sierpinski网络[4], 并已得到准确的捕获时间的表达式以及对应网络的扩散概率.

本文基于吴波等[5]联合Sierpinski垫片的研究思路，建立联合三分Sierpinski垫片模型JSG3(S,g)，其中S代表模型变量，g代表网络的迭代次数.在联合Sierpinski垫片模型基础上得到JSG3(S,g)的平均捕获时间.下面的内容我们分成以下几个部分：第一部分，简要介绍文献[3]的三分Sierpinski垫片SG3(g)，在此基础上，介绍如何构建联合三分Sierpinski垫片模型JSG3(S,g).在第二部分、第三部分，首先简要介绍矩阵算法，其次计算JSG3(S,g)的平均捕获时间，得到一般表达式.

1 联合三分谢尔宾斯基(Sierpinski)模型的构建

1.1 SG3(g)模型

SG3(g)模型是一类特殊的分形模型，是Sierpinski垫片的一种延伸.从图1所示的SG3(0)、SG3(1)、SG3(2)这三代，我们可以看出SG3(g)的迭代模式，以及良好的自相似性：SG3(g)可以由6个SG3(g-1)拼接而成.SG3(g)中的节点总数目与连边数分别用N(g)与E(g)来表示，可以根据以往的文献[3]直接得到

图1中，最左边的图形为SG3(0),右边两个为经历两代后产生的图形，分别为SG3(1)和SG3(2).图中的▲ 和◆为新产生的节点.

图1 SG3(g)

1.2 JSG3(S,g)模型的构建

在简要介绍SG3(g)模型之后，我们来看如何构建联合三分Sierpinski模型JSG3(S,g)，该模型由m个三角形拼接而成，拼接方式由模型变量S决定，如图2所示有两种模型变量S0和S1(S0由三个三角形组成，S1由6个三角形组成)；其次在每一个三角形中嵌入一个SG3(g)，即建成JSG3(S,g)模型.

图2 模型变量S为0,1的图形

(1)

由于JSG3(S,g)是由m个SG3(g)组成的，所以总边数满足

E(S,g)=mE(g).

(2)

1.3 联合三分Sierpinski垫片JSG3(S,g)的特殊例子

由图2，我们可以看出联合三分Sierpinski垫片JSG3(S,g)是经典三分Sierpinski垫片SG3(g)的一种拓展：JSG3(S,g)=SG3(g+1).但是联合三分Sierpinski垫片JSG3(S,g)的作用更大.我们经常会遇到被破坏的网络，如，将全局网络进行垂直切割与水平切割后剩余的网络.在这里我们对SG3(g)进行如图3所示的两种切割l1和l2，丢弃切割线以上的图形(包括切割线上的边，但切割线上的点保留)，将最右边图形分别定义为模型变量S2和S3.切割后所遗存的网络分别记为JSG3(S2,g-1)和JSG3(S3,g-1).相应地，根据等式(1)和(2)，可以得到

N(S2,g-1)=7·6g+2,E(S2,g-1)=15·6g；

图3 两种三分Sierpinski垫片SG3(g)被破坏后剩余的网络

上述例子告诉我们，联合三分Sierpinski垫片JSG3(S,g)模型可以被用来构建一种被破坏之后剩余的三分Sierpinski垫片SG3(g).

2 联合三分谢尔宾斯基(Sierpinski)垫片的平均捕获时间

2.1 矩阵算法

我们考虑在任意连通网络G上的无偏度马尔可夫随机游走.设网络G的节点数为N，连边数为E.从任意非捕获节点能够以等同的概率跳到其邻居节点，则每一步的转移概率pij是该节点度的倒数，即

其中，pij为从i一步跳到j的概率，i～j表示i有连边与j直接相连.

我们用Ti来表示在网络G上节点i到捕获点的平均首次通过时间.不失一般性，我们设节点1为捕获点.任意非捕获节点i在n步跳跃后，依然未被捕获点捕获的概率满足后科尔莫哥洛夫方程，即Ti满足下列等式:

(3)

接下来，我们定义过渡概率矩阵(无陷阱点)为M=(pij)N×N.由于我们将节点1设为捕获节点，所以记该过渡概率矩阵为MT，也就是移除矩阵M关于节点1的行和列，即移除M第一行以及第一列后得到的矩阵.然后，令

T=(T2,T3,…,TN),

那么式(3)可以表示成

T=MTT+e，

(4)

其中，T和e是N-1维列向量，并且向量e的所有元素是1.式(4)可以转化成

T=(I-MT)-1e，

其中，aij表示矩阵(I-MT)-1中i行j列元素.

2.2 求解

我们将从A到B,C的平均捕获时间记为FA(g)，从A到D,E的平均捕获时间记为F'(g)，从D,F,G和I到B或C的平均捕获时间分别记为FD(g),FF(g),FG(g)和FI(g).根据无偏度随机游走定义以及网络的对称性，我们建立以下方程组：

解以上方程组，我们得到

由SG3(g)的自相似性，可知F'(g)就是在g-1代SG3(g-1)网络中从A到B,C的平均捕获时间，所以可以得出下列关系式：

FA(g-1)=F'(g).

在初始网络SG3(0)中，从A到B,C的平均捕获时间是1，根据上式的迭代关系，在SG3(g)网络中，从A到B,C的平均捕获时间为

由SG3(g)网络的对称性，我们可以得到关系式

解上述方程组，可以得到

2.3 计算JSG3(S,g)的平均捕获时间

其中，Ta,b(S,0)代表在模型S中从a到b的平均捕获时间.根据以上的分析，我们可以得到

(5)

(6)

并且Td(S)可以通过矩阵算法计算出来.如此式(6)可以进一步简化成

(7)

(8)

由于Td(S)与Ttotal(S,0)都只由模型变量S决定，并且可以通过矩阵算法求出来，因此平均捕获时间也可以得到:

(9)

3 结论

本文主要是在文献[5]联合Sierpinski垫片研究思路的基础上,将其结果推广到联合三分Sierpinski垫片上，得到了在该网络上无偏随机游走的平均捕获时间的解析式：式(8)和式(9).并通过解析式发现，该网络的平均捕获时间与模型变量S有关.