左半三级Sierpinski垫片上的平均捕获时间

操 芳，吴 波

（南京财经大学 应用数学学院，南京 210023）

0 引言

近年来，复杂网络因其在自然界中的广泛应用而越来越受到人们的关注.在复杂网络的研究中，一个重要的问题就是网络的扩散效率，而平均捕获时间就是一个很好的研究指标，它表示的是一个随机游走者从网络任意节点到达网络陷阱点的平均首达时间［1-2］.众多学者对于加权三角网络［3］、加权树状网络［4］、（2，2）花网络［5］、Koch 网络［6］等进行研究，获得了这些网络上的平均捕获时间的精确解析表达式和对应网络上的扩散效率.上述网络都是完整的网络，具有全局自相似结构，但自然界中复杂网络往往会受到攻击造成网络的损坏或缺失，因此，研究相关残损网络上的扩散效率很有意义.吴波等［7］考虑了Sierpinski垫片上的垂直切割，通过切割，得到剩余的左半网络，研究了左半Sierpinski垫片上的平均捕获时间并得到了该残余网络上的扩散效率.

本文基于Sierpinski 垫片上的切割思想，研究了三级Sierpinski 垫片上的切割，得到了左半三级Sierpinski垫片，并考虑了该残余网络上的平均捕获时间.通过比较左半三级Sierpinski垫片和原始网络上的平均捕获时间的增长趋势，发现它们的平均捕获时间的增长趋势大致一致，说明在大规模尺度下，对于三级Sierpinski垫片受到攻击后，该残余网络的扩散效率基本没有影响.

1 左半三级Sierpinski垫片的构建

左半三级Sierpinski垫片的构建：设第t代三级Sierpinski垫片为S3(t)，迭代方法如下：

（1）当t = 0，S3(0)是一个等边三角形，三个节点分别是A，B，C；

（2）当t ≥1，S3(t)由S3(t - 1)通过以下步骤产生：首先将S3(t - 1)中每个小等边三角形三等分，然后再将等边节点以平行于对边的方式依次连接，并挖去中间的三个小等边三角形.

对于第一代Sierpinski 三角形S3(1)，将第一代新产生的7 个节点依次标记为D，E，F，G，H，I，J.除此之外，对于S3(t)中所有的节点，从上到下从左到右依次标上序号1，2，3，….

三级Sierpinski垫片上的切割：设第t代的一半的三级Sierpinski三角形为H3(t)，H3(t)是将S3(t)由其对称轴垂直分割，其中在对称轴上的边不属于H3(t)，分割后留下的左半部分即为H3(t)，如图1所示.

图1 S3(t)与H3(t)从t = 0到t = 2连续三代的迭代图形

对于第 t 代 S3(t)，设 Nt为 S3(t)中的总节点数，Et为 S3(t)中的总边数；对于第 t 代 H3(t)，H3(t)中的总节点数，E~t为H3(t)中的总边数.根据S3(t)的构建方法以及迭代特征，可以得出以下拓扑性质：

为了方便下面的计算，这里将图1 中的A 点以及以A 点为顶点的最小三角形的三条边去掉，所组成

图2 S′3(t)与H′3(t)的图形特征

2 平均捕获时间的解析表达式

为了研究在三级Sierpinski 垫片上的随机无偏游走，并计算左半三级Sierpinski 垫片H3(t)上的平均捕获时间，将给出一些定义和记号.

在图1中，记节点A(1)为随机无偏游走的捕获点，Pij为随机游走过程中节点i到节点j的概率，则

其中：di为节点i的度.

设Tij(t)和别表示节点i 到节点j 在第t 代S3(t)与H3(t)上的平均首达时间，也是在无偏随机游走中游走者从节点i 到节点j 的期望时间；Ti(t)和为节点i（非捕获点）到捕获点的捕获时间；别为S3(t)和H3(t)的平均捕获时间，可分别表示为：

由参考文献［8］，可得

由方程组（3）可知，为了求出H3(t)上的平均捕获时要先求

对式（7）化简得

其中：Ti→2,3为S3(t)中节点i到节点2或节点3的平均首达时间.

再结合式（6）得

因此

根据三级Sierpinski垫片S3(t)的自相似性，S3(t)是由6个S3(t - 1)组成，这里将这6个三角形区域分别标记为 Γt1-1,Γt2-1,…,Γt6-1；对于每个 S3(t - 1)又是由 6 个 S3(t - 2)区域组成，可以依次标记为Γt1-2,Γt2-2,…,Γt6-2，S3(t)也是由62个Γtx-2(1 ≤ x ≤ 6)区域组成；由此可见，对于S3(t)中每个S3(y)(0 ≤ y ≤t)，都是由6 个S3(y - 1)区域组成，依次标记Γy1-1,Γy2-1,…,Γy6-1，S3(t)是由6t-y个Γyx(1 ≤ x ≤ 6)组成的图形.因此，根据这种自相似性，将S3(t)划分为不同的区域.

此外，对于S3(t)中的三角形区域Γy1(1 ≤y ≤t)，Γy1三角形上包含了节点A(1)和另外两个节点，这里将节点A(1)记为ay，其余两个节点分别记为by,cy，Γy1三角形内的剩下7个节点从左到右从上到下依次标记为 dy(by- 1)，ey(cy- 1)，fy，gy，hy，iy，jy.对于三角形区域 Γy1+1，显然 Γy1+1包含三角形区域 Γy1，将节点A(1)记为ay+1，Γy1中的节点by,cy在Γy1+1中变为dy+1，ey+1，如图3所示.

图3 S3(t)的划分与三角形区域Γ1y

在 S3(t)中，设 F(t)为节点 A 到节点 B 或节点 C 的平均首达时间，F′(t)为节点 A 到节点 D 或节点 E 的平均首达时间，FD，FE，FF，FG，FH，FI，FJ分别为节点D，E，F，G，H，I，J到节点B 或节点C 的平均首达时间.基于无偏Markovian随机游走以及S3(t)网络的自相似性，有

与第t - 1代节点A到节点B或节点C的平均首达时间相等，即

下面考虑三角形区域Γ1y(1 ≤y ≤t).设节点ay,by,cy为捕获点，T′i(y)为节点i的平均捕获时间，那么对于对称轴上并在三角形区域Γ1y上的节点gy，有

由式（13）可得

进一步，将考虑从节点gy出发，到达三个捕获点ay，by，cy的概率，根据网络的对称性和自相似性，有

基于以上分析，在三级Sierpinski 垫片S3(t)网络的无偏随机游走过程中，从对称轴上的节点gy出发，游走者概率经间到达捕获节点A，分别概率到达捕获节点B，C，且到达节点B或C的捕获时间相等.因此，从节点gy出发到达捕获点的捕获时间为

代入式（17）得

由该分形无标度网络的迭代特征，在S3(t)中观察到对称轴上的节点gy(t)(1 ≤y ≤t)共有(2y- 1)个节点，其中gt(t)有1个节点，gt-1(t)有2个节点，gt-2(t)有22个节点，…，g1(t)有2y-1个节点.由此可得

将式（1），（4），（19）带入式（11）得

将式（20）带入式（3）中，即可得到在H3(t)上的平均捕获时表达式

由于

3 结论

本文主要考虑受到攻击后的左半三级Sierpinski 垫片的分形网络上的捕获问题，通过分析和计算，可以得到该网络上平均捕获时间的解析表达式.在大规模网络中，平均捕获时间随着网络的规模的增长近似呈幂律函数增长，且幂指据本文获得的左半三级Sierpinski 垫片H3(t)上平均捕获时表达式以及由文献［5］得到的原始网络三级Sierpinski垫片S3(t)上平均捕获时表达式进行作图对比，如图4所示.

图4 S3(t)与H3(t)上的平均捕获时间数值模拟图