左半三級(jí)Sierpinski墊片上的平均捕獲時(shí)間

操 芳，吳 波

（南京財(cái)經(jīng)大學(xué) 應(yīng)用數(shù)學(xué)學(xué)院，南京 210023）

0 引言

近年來，復(fù)雜網(wǎng)絡(luò)因其在自然界中的廣泛應(yīng)用而越來越受到人們的關(guān)注.在復(fù)雜網(wǎng)絡(luò)的研究中，一個(gè)重要的問題就是網(wǎng)絡(luò)的擴(kuò)散效率，而平均捕獲時(shí)間就是一個(gè)很好的研究指標(biāo)，它表示的是一個(gè)隨機(jī)游走者從網(wǎng)絡(luò)任意節(jié)點(diǎn)到達(dá)網(wǎng)絡(luò)陷阱點(diǎn)的平均首達(dá)時(shí)間［1-2］.眾多學(xué)者對(duì)于加權(quán)三角網(wǎng)絡(luò)［3］、加權(quán)樹狀網(wǎng)絡(luò)［4］、（2，2）花網(wǎng)絡(luò)［5］、Koch 網(wǎng)絡(luò)［6］等進(jìn)行研究，獲得了這些網(wǎng)絡(luò)上的平均捕獲時(shí)間的精確解析表達(dá)式和對(duì)應(yīng)網(wǎng)絡(luò)上的擴(kuò)散效率.上述網(wǎng)絡(luò)都是完整的網(wǎng)絡(luò)，具有全局自相似結(jié)構(gòu)，但自然界中復(fù)雜網(wǎng)絡(luò)往往會(huì)受到攻擊造成網(wǎng)絡(luò)的損壞或缺失，因此，研究相關(guān)殘損網(wǎng)絡(luò)上的擴(kuò)散效率很有意義.吳波等［7］考慮了Sierpinski墊片上的垂直切割，通過切割，得到剩余的左半網(wǎng)絡(luò)，研究了左半Sierpinski墊片上的平均捕獲時(shí)間并得到了該殘余網(wǎng)絡(luò)上的擴(kuò)散效率.

本文基于Sierpinski 墊片上的切割思想，研究了三級(jí)Sierpinski 墊片上的切割，得到了左半三級(jí)Sierpinski墊片，并考慮了該殘余網(wǎng)絡(luò)上的平均捕獲時(shí)間.通過比較左半三級(jí)Sierpinski墊片和原始網(wǎng)絡(luò)上的平均捕獲時(shí)間的增長(zhǎng)趨勢(shì)，發(fā)現(xiàn)它們的平均捕獲時(shí)間的增長(zhǎng)趨勢(shì)大致一致，說明在大規(guī)模尺度下，對(duì)于三級(jí)Sierpinski墊片受到攻擊后，該殘余網(wǎng)絡(luò)的擴(kuò)散效率基本沒有影響.

1 左半三級(jí)Sierpinski墊片的構(gòu)建

左半三級(jí)Sierpinski墊片的構(gòu)建：設(shè)第t代三級(jí)Sierpinski墊片為S3(t)，迭代方法如下：

（1）當(dāng)t = 0，S3(0)是一個(gè)等邊三角形，三個(gè)節(jié)點(diǎn)分別是A，B，C；

（2）當(dāng)t ≥1，S3(t)由S3(t - 1)通過以下步驟產(chǎn)生：首先將S3(t - 1)中每個(gè)小等邊三角形三等分，然后再將等邊節(jié)點(diǎn)以平行于對(duì)邊的方式依次連接，并挖去中間的三個(gè)小等邊三角形.

對(duì)于第一代Sierpinski 三角形S3(1)，將第一代新產(chǎn)生的7 個(gè)節(jié)點(diǎn)依次標(biāo)記為D，E，F(xiàn)，G，H，I，J.除此之外，對(duì)于S3(t)中所有的節(jié)點(diǎn)，從上到下從左到右依次標(biāo)上序號(hào)1，2，3，….

三級(jí)Sierpinski墊片上的切割：設(shè)第t代的一半的三級(jí)Sierpinski三角形為H3(t)，H3(t)是將S3(t)由其對(duì)稱軸垂直分割，其中在對(duì)稱軸上的邊不屬于H3(t)，分割后留下的左半部分即為H3(t)，如圖1所示.

圖1 S3(t)與H3(t)從t = 0到t = 2連續(xù)三代的迭代圖形

對(duì)于第 t 代 S3(t)，設(shè) Nt為 S3(t)中的總節(jié)點(diǎn)數(shù)，Et為 S3(t)中的總邊數(shù)；對(duì)于第 t 代 H3(t)，H3(t)中的總節(jié)點(diǎn)數(shù)，E~t為H3(t)中的總邊數(shù).根據(jù)S3(t)的構(gòu)建方法以及迭代特征，可以得出以下拓?fù)湫再|(zhì)：

為了方便下面的計(jì)算，這里將圖1 中的A 點(diǎn)以及以A 點(diǎn)為頂點(diǎn)的最小三角形的三條邊去掉，所組成

圖2 S′3(t)與H′3(t)的圖形特征

2 平均捕獲時(shí)間的解析表達(dá)式

為了研究在三級(jí)Sierpinski 墊片上的隨機(jī)無偏游走，并計(jì)算左半三級(jí)Sierpinski 墊片H3(t)上的平均捕獲時(shí)間，將給出一些定義和記號(hào).

在圖1中，記節(jié)點(diǎn)A(1)為隨機(jī)無偏游走的捕獲點(diǎn)，Pij為隨機(jī)游走過程中節(jié)點(diǎn)i到節(jié)點(diǎn)j的概率，則

其中：di為節(jié)點(diǎn)i的度.

設(shè)Tij(t)和別表示節(jié)點(diǎn)i 到節(jié)點(diǎn)j 在第t 代S3(t)與H3(t)上的平均首達(dá)時(shí)間，也是在無偏隨機(jī)游走中游走者從節(jié)點(diǎn)i 到節(jié)點(diǎn)j 的期望時(shí)間；Ti(t)和為節(jié)點(diǎn)i（非捕獲點(diǎn)）到捕獲點(diǎn)的捕獲時(shí)間；別為S3(t)和H3(t)的平均捕獲時(shí)間，可分別表示為：

由參考文獻(xiàn)［8］，可得

由方程組（3）可知，為了求出H3(t)上的平均捕獲時(shí)要先求

對(duì)式（7）化簡(jiǎn)得

其中：Ti→2,3為S3(t)中節(jié)點(diǎn)i到節(jié)點(diǎn)2或節(jié)點(diǎn)3的平均首達(dá)時(shí)間.

再結(jié)合式（6）得

因此

根據(jù)三級(jí)Sierpinski墊片S3(t)的自相似性，S3(t)是由6個(gè)S3(t - 1)組成，這里將這6個(gè)三角形區(qū)域分別標(biāo)記為 Γt1-1,Γt2-1,…,Γt6-1；對(duì)于每個(gè) S3(t - 1)又是由 6 個(gè) S3(t - 2)區(qū)域組成，可以依次標(biāo)記為Γt1-2,Γt2-2,…,Γt6-2，S3(t)也是由62個(gè)Γtx-2(1 ≤ x ≤ 6)區(qū)域組成；由此可見，對(duì)于S3(t)中每個(gè)S3(y)(0 ≤ y ≤t)，都是由6 個(gè)S3(y - 1)區(qū)域組成，依次標(biāo)記Γy1-1,Γy2-1,…,Γy6-1，S3(t)是由6t-y個(gè)Γyx(1 ≤ x ≤ 6)組成的圖形.因此，根據(jù)這種自相似性，將S3(t)劃分為不同的區(qū)域.

此外，對(duì)于S3(t)中的三角形區(qū)域Γy1(1 ≤y ≤t)，Γy1三角形上包含了節(jié)點(diǎn)A(1)和另外兩個(gè)節(jié)點(diǎn)，這里將節(jié)點(diǎn)A(1)記為ay，其余兩個(gè)節(jié)點(diǎn)分別記為by,cy，Γy1三角形內(nèi)的剩下7個(gè)節(jié)點(diǎn)從左到右從上到下依次標(biāo)記為 dy(by- 1)，ey(cy- 1)，fy，gy，hy，iy，jy.對(duì)于三角形區(qū)域 Γy1+1，顯然 Γy1+1包含三角形區(qū)域 Γy1，將節(jié)點(diǎn)A(1)記為ay+1，Γy1中的節(jié)點(diǎn)by,cy在Γy1+1中變?yōu)閐y+1，ey+1，如圖3所示.

圖3 S3(t)的劃分與三角形區(qū)域Γ1y

在 S3(t)中，設(shè) F(t)為節(jié)點(diǎn) A 到節(jié)點(diǎn) B 或節(jié)點(diǎn) C 的平均首達(dá)時(shí)間，F(xiàn)′(t)為節(jié)點(diǎn) A 到節(jié)點(diǎn) D 或節(jié)點(diǎn) E 的平均首達(dá)時(shí)間，F(xiàn)D，F(xiàn)E，F(xiàn)F，F(xiàn)G，F(xiàn)H，F(xiàn)I，F(xiàn)J分別為節(jié)點(diǎn)D，E，F(xiàn)，G，H，I，J到節(jié)點(diǎn)B 或節(jié)點(diǎn)C 的平均首達(dá)時(shí)間.基于無偏Markovian隨機(jī)游走以及S3(t)網(wǎng)絡(luò)的自相似性，有

與第t - 1代節(jié)點(diǎn)A到節(jié)點(diǎn)B或節(jié)點(diǎn)C的平均首達(dá)時(shí)間相等，即

下面考慮三角形區(qū)域Γ1y(1 ≤y ≤t).設(shè)節(jié)點(diǎn)ay,by,cy為捕獲點(diǎn)，T′i(y)為節(jié)點(diǎn)i的平均捕獲時(shí)間，那么對(duì)于對(duì)稱軸上并在三角形區(qū)域Γ1y上的節(jié)點(diǎn)gy，有

由式（13）可得

進(jìn)一步，將考慮從節(jié)點(diǎn)gy出發(fā)，到達(dá)三個(gè)捕獲點(diǎn)ay，by，cy的概率，根據(jù)網(wǎng)絡(luò)的對(duì)稱性和自相似性，有

基于以上分析，在三級(jí)Sierpinski 墊片S3(t)網(wǎng)絡(luò)的無偏隨機(jī)游走過程中，從對(duì)稱軸上的節(jié)點(diǎn)gy出發(fā)，游走者概率經(jīng)間到達(dá)捕獲節(jié)點(diǎn)A，分別概率到達(dá)捕獲節(jié)點(diǎn)B，C，且到達(dá)節(jié)點(diǎn)B或C的捕獲時(shí)間相等.因此，從節(jié)點(diǎn)gy出發(fā)到達(dá)捕獲點(diǎn)的捕獲時(shí)間為

代入式（17）得

由該分形無標(biāo)度網(wǎng)絡(luò)的迭代特征，在S3(t)中觀察到對(duì)稱軸上的節(jié)點(diǎn)gy(t)(1 ≤y ≤t)共有(2y- 1)個(gè)節(jié)點(diǎn)，其中g(shù)t(t)有1個(gè)節(jié)點(diǎn)，gt-1(t)有2個(gè)節(jié)點(diǎn)，gt-2(t)有22個(gè)節(jié)點(diǎn)，…，g1(t)有2y-1個(gè)節(jié)點(diǎn).由此可得

將式（1），（4），（19）帶入式（11）得

將式（20）帶入式（3）中，即可得到在H3(t)上的平均捕獲時(shí)表達(dá)式

由于

3 結(jié)論

本文主要考慮受到攻擊后的左半三級(jí)Sierpinski 墊片的分形網(wǎng)絡(luò)上的捕獲問題，通過分析和計(jì)算，可以得到該網(wǎng)絡(luò)上平均捕獲時(shí)間的解析表達(dá)式.在大規(guī)模網(wǎng)絡(luò)中，平均捕獲時(shí)間隨著網(wǎng)絡(luò)的規(guī)模的增長(zhǎng)近似呈冪律函數(shù)增長(zhǎng)，且冪指據(jù)本文獲得的左半三級(jí)Sierpinski 墊片H3(t)上平均捕獲時(shí)表達(dá)式以及由文獻(xiàn)［5］得到的原始網(wǎng)絡(luò)三級(jí)Sierpinski墊片S3(t)上平均捕獲時(shí)表達(dá)式進(jìn)行作圖對(duì)比，如圖4所示.

圖4 S3(t)與H3(t)上的平均捕獲時(shí)間數(shù)值模擬圖