加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的平均首到達(dá)時間與平均吸收時間

景興利，趙彩紅，凌 翔

(1.濟(jì)源職業(yè)技術(shù)學(xué)院，河南 濟(jì)源 454650；2.合肥工業(yè)大學(xué)汽車與交通工程學(xué)院，合肥 230009)

0 引言

1 加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走

接下來對加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走進(jìn)行分析。在加權(quán)網(wǎng)絡(luò)上，每個時間步，一個隨機(jī)行走粒子從當(dāng)前位置以概率pij=wij/si進(jìn)行帶偏隨機(jī)行走，即：每個時間步隨機(jī)行走粒子從節(jié)點i向節(jié)點j以概率pij進(jìn)行傳輸選擇。令P表示網(wǎng)絡(luò)G上隨機(jī)行走的傳輸概率矩陣，則

P=S-1W

(1)

顯然地，當(dāng)G為規(guī)則網(wǎng)絡(luò)時P為對稱矩陣，否則P為非對稱矩陣。令：

(2)

令λ1,λ2,…,λN表示矩陣Γ在G上相應(yīng)的N個特征向量，重新整理為1=λ1>λ2≥…≥λN≥-1，其相應(yīng)的標(biāo)準(zhǔn)化、正交特征向量表示為ψ1,ψ2,…,ψN，其中ψi=(ψi1,ψi2,…,ψiN)表示Ψ的第i列向量。則

ΨTΨ=ΨΨT=E

(3)

令E表示N階單位矩陣。根據(jù)實對稱矩陣的性質(zhì)有：

ΨTΓΨ=diag[λ1,λ2,…,λN]

(4)

Γ=Ψdiag[λ1,λ2,…,λN]ΨT

(5)

通過上邊的分析，可以將矩陣P進(jìn)一步表示為

(6)

以上對加權(quán)網(wǎng)絡(luò)上隨機(jī)行走模型及特性進(jìn)行了分析，得到了傳輸概率矩陣P關(guān)于Ψ和S的關(guān)系式，接下來利用這些性質(zhì)對加權(quán)網(wǎng)絡(luò)上隨機(jī)行走效率進(jìn)行分析。

2 加權(quán)網(wǎng)絡(luò)上的平均首到達(dá)時間與平均吸收時間

本節(jié)通過圖譜理論方法計算含有N個節(jié)點的加權(quán)網(wǎng)絡(luò)G上的任意兩節(jié)點間的MFPT。為了方便起見，將G的N個節(jié)點標(biāo)注為1,2,…,N。不失一般性地，令TiN表示從任一節(jié)點i到任一節(jié)點N的MFPT。在給出TiN后我們將進(jìn)一步分析特殊節(jié)點的平均吸收時間(Average Trapping Time,ATT)。令TN表示節(jié)點N的ATT，即假定在網(wǎng)絡(luò)G上有一特殊吸收節(jié)點N，TN為網(wǎng)絡(luò)G上所有節(jié)點i到達(dá)節(jié)點N的MFPT的平均值。ATT在復(fù)雜網(wǎng)絡(luò)上隨機(jī)行走研究中具有非常重要的意義。

加權(quán)網(wǎng)絡(luò)G上的隨機(jī)行走是馬爾科夫過程[22]，從節(jié)點i到節(jié)點N的MFPT(TiN)可以被精確通過基礎(chǔ)矩陣Z中的一系列元素ziN描述，矩陣Z被定義為

Z=(E-P+R)-1

(7)

其中,R為πΤ的行向量。則由文獻(xiàn)[23]知：

(8)

其中,πN是靜態(tài)矩陣為π=(π1，π2，…，πN)的一個列向量，其每個元素通過如下方式求得：令Pt表示P的t次冪，那么，一個隨機(jī)行走粒子從節(jié)點i出發(fā)經(jīng)過t個時間步到達(dá)節(jié)點N的概率為表示為(pt)iN，(pt)iN為Pt它的第i行第N列元素。由式(6)可得：

(9)

(10)

當(dāng)t→∞時，可得：

(11)

因此，加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的靜態(tài)矩陣可進(jìn)一步表示為

(12)

進(jìn)而，由文獻(xiàn)[22]的關(guān)于靜態(tài)概率矩陣的定義得

(13)

為求TiN，需要先給出Z的表達(dá)式。而Z中的R與P對應(yīng)的式(6)與(13)均為關(guān)于Ψ與S的表達(dá)式。因此我們也將E也表示為關(guān)于Ψ和S的關(guān)系式，則由式(3)知

(14)

那么，將(6)(13)和(14)帶入式(7)得

(15)

其中，ziN可進(jìn)一步表示為

(16)

另外，Γ的一個特征值為λ1=1，假設(shè)對應(yīng)的特征向量為ψ1。從式(2)(13)及P1=1,可得

(17)

那么通過上邊的分析，TiN可表示為

(18)

式(18)的形式和文獻(xiàn)[17]相同，但從另外一個角度給出了加權(quán)網(wǎng)絡(luò)上MFPT解析公式，且當(dāng)w0=1時，含義與文獻(xiàn)[17]相同，但本文的結(jié)果更具廣泛性。從式(18)知MFPT(TiN)的大小與目的地節(jié)點權(quán)重及邊權(quán)系數(shù)等有關(guān)。結(jié)合度不相關(guān)加權(quán)網(wǎng)絡(luò)的點權(quán)和總點權(quán)的數(shù)學(xué)表達(dá)式，進(jìn)一步對式(18)進(jìn)行處理得：

(19)

從式(19)可看出，在度不相關(guān)加權(quán)網(wǎng)絡(luò)上影響MFPT的網(wǎng)絡(luò)結(jié)構(gòu)的重要因素有網(wǎng)絡(luò)大小，網(wǎng)絡(luò)邊權(quán)控制系數(shù)θ。而網(wǎng)絡(luò)邊權(quán)控制系數(shù)w0對網(wǎng)絡(luò)TiN的大小沒有影響。

ATT在認(rèn)識網(wǎng)絡(luò)上隨機(jī)行走特性中也具有非常重要的意義。在文獻(xiàn)[17]，[24]中已有呈現(xiàn)。根據(jù)ATT的定義，TN的表達(dá)式可表示為

(20)

考慮式(3)、(4)，式(20)可一步表示為

(21)

利用柯西不等式，可得TN的下界為

(22)

通過式(22)知，ATT的下界與吸收點權(quán)重及網(wǎng)絡(luò)總點權(quán)有關(guān)。進(jìn)一步分析，與網(wǎng)絡(luò)大小N及其平均度、吸收點度大小dN、網(wǎng)絡(luò)邊權(quán)控制系數(shù)θ有關(guān)，而與網(wǎng)絡(luò)邊權(quán)控制系數(shù)w0無關(guān)，這與任意兩個節(jié)點間的MFPT的性質(zhì)相同。

(23)

則將(23)代入(22)得

(24)

通過以上對〈dθ+1〉的分析知，在度不相關(guān)網(wǎng)絡(luò)上的隨機(jī)行走的節(jié)點的TN與度分布指數(shù)有密切關(guān)系。特別地，文獻(xiàn)[17]給出了網(wǎng)絡(luò)吸收節(jié)點度為dmax時TN的分析結(jié)果。

3 仿真分析

為了進(jìn)一步認(rèn)識度不相關(guān)加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的特性，通過計算機(jī)仿真作進(jìn)一步探索。不失一般性地，對第1節(jié)提出的網(wǎng)絡(luò)模型，利用BA無標(biāo)度網(wǎng)絡(luò)模型建立加權(quán)網(wǎng)絡(luò)模型[25]，其度分布服從P(d)～d-3。首先，建立一個N=1 000，平均度〈d〉≈10的BA無權(quán)網(wǎng)絡(luò)；然后，根據(jù)第1節(jié)提出的方法即可產(chǎn)生一個度不相關(guān)加權(quán)網(wǎng)絡(luò)G。通過分析知，當(dāng)θ=0,w0=1時，G退化為BA無權(quán)網(wǎng)絡(luò)；當(dāng)w0=0時，G上所有邊的權(quán)重均為0，無意義。

下邊對G上隨機(jī)行走進(jìn)行計算機(jī)仿真。分析不同θ值下，網(wǎng)絡(luò)G上隨機(jī)行走ATT的特性，我們對其仿真，仿真結(jié)果見圖1，圖1為在雙對數(shù)坐標(biāo)系下表示的仿真及式(22)表示的TN的下界的結(jié)果。從圖1可以看出，ATT的大小與吸收節(jié)點的度大小有密切關(guān)系，當(dāng)θ>-1時，吸收點的度越大ATT越小，吸收點的度越小ATT越大，呈反比關(guān)系，隨著θ值的增大，不同大小度的節(jié)點的隨機(jī)行走效率差異擴(kuò)大；當(dāng)θ<-1時，吸收點的度的大小與相應(yīng)的ATT呈正比關(guān)系，隨著θ值的減小，不同大小度的節(jié)點的隨機(jī)行走效率差異擴(kuò)大；當(dāng)θ=-1時，所有節(jié)點的ATT大小相同。呈現(xiàn)這種仿真結(jié)果是由于ATT的大小與網(wǎng)絡(luò)結(jié)構(gòu)有著密切關(guān)系，θ取值改變了網(wǎng)絡(luò)中的節(jié)點的連通性，當(dāng)網(wǎng)絡(luò)的連通性較好時，到達(dá)吸收節(jié)點的概率就大，所用的時間就少，反之時間就多。顯然地，當(dāng)θ值不變時，w0的取值大小，對于所有邊權(quán)的改變是線性、同比例改變大，相對來說沒有改變網(wǎng)絡(luò)節(jié)點之間的連通性，因此，網(wǎng)絡(luò)上節(jié)點的ATT無變化。由圖1可以看出，仿真結(jié)果與式(22)的解析結(jié)果的分析一致。

N=1 000，〈d〉≈10，w0=1，S和A分別對應(yīng)解析和仿真情況。圖1 在雙對數(shù)坐標(biāo)系上表示的網(wǎng)絡(luò)G上取不同的權(quán)重系數(shù)θ時，ATT與吸收節(jié)點度d的關(guān)系圖

根據(jù)式(22)知，ATT大小與網(wǎng)絡(luò)大小N有密切關(guān)系。為使結(jié)果更加直觀，在θ=0.5,w0=1的情況下，我們在仿真時對網(wǎng)絡(luò)G大小進(jìn)行調(diào)節(jié)。網(wǎng)絡(luò)G大小分別取為N=500,1 000,2 000，〈d〉≈10。仿真結(jié)果見圖2。由圖2知，在節(jié)點度大小相等的情況下，相應(yīng)節(jié)點的ATT隨著網(wǎng)絡(luò)規(guī)模的增大而增大。

網(wǎng)絡(luò)的連通性對網(wǎng)絡(luò)上隨機(jī)行走的效率有著很大影響。圖3取不同網(wǎng)絡(luò)平均度〈d〉的相同網(wǎng)絡(luò)規(guī)模上的隨機(jī)行走就行了仿真，其中N=1 000，θ=0.3,w0=1，〈d〉分別取6,10,14。從仿真圖可以看出，在網(wǎng)絡(luò)節(jié)點總數(shù)相同時，網(wǎng)絡(luò)平均度越大，相同的節(jié)點度的ATT越小。這是由于在網(wǎng)絡(luò)節(jié)點總數(shù)相同時，網(wǎng)絡(luò)平均度〈d〉越大，網(wǎng)絡(luò)上節(jié)點之間的連通性越好，這樣在隨機(jī)行走時到達(dá)某個節(jié)點的概率就會隨之增大。因此，在網(wǎng)絡(luò)節(jié)點總數(shù)相同時，網(wǎng)絡(luò)平均度越大，則其節(jié)點的ATT普遍較網(wǎng)絡(luò)平均度小的相同度的節(jié)點的ATT小，隨機(jī)行走效率越高。

〈d〉≈10，θ=0.5,w0=1圖2 在雙對數(shù)坐標(biāo)系表示的不同網(wǎng)絡(luò)節(jié)點數(shù)(N)的網(wǎng)絡(luò)G上，ATT與吸收節(jié)點度d的關(guān)系仿真圖

N=1 000，θ=0.3,w0=1圖3 在雙對數(shù)坐標(biāo)系表示的不同大小的網(wǎng)絡(luò)平均度〈d〉的網(wǎng)絡(luò)G上，ATT與吸收節(jié)點度d的關(guān)系仿真圖

4 結(jié)論

本文運用圖譜理論的方法研究了度不相關(guān)加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走過程。與文獻(xiàn)[11]關(guān)注的加權(quán)網(wǎng)絡(luò)上隨機(jī)行走的MFRT指標(biāo)不同，本文對MFPT、ATT兩個重要刻畫指標(biāo)進(jìn)行了分析。通過分析，我們發(fā)現(xiàn)網(wǎng)絡(luò)的權(quán)重系數(shù)θ、吸收點度的大小、網(wǎng)絡(luò)大小和網(wǎng)絡(luò)平均度指標(biāo)值的大小有關(guān)，而權(quán)重系數(shù)w0與兩個指標(biāo)值的大小無關(guān)。這主要是因為θ值的大小改變了網(wǎng)絡(luò)節(jié)點的連通性，而w0沒有。對上述分析結(jié)果本文進(jìn)行了計算機(jī)仿真驗證，解析結(jié)果與仿真結(jié)果一致。本文的研究對進(jìn)一步了解加權(quán)網(wǎng)絡(luò)上的隨機(jī)行走行為和相關(guān)網(wǎng)絡(luò)動力學(xué)有意義。